A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 331-346.

A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a 3-approximation algorithm for unit disk graphs and a 2-approximation algorithm for penny graphs.

DOI : 10.1051/ita/2011106
Classification : 05C69, 05C75, 68W25, 68Q25
Mots-clés : unit disk graphs, unit coin graphs, penny graphs, independent set, clique partition, approximation algorithms 
@article{ITA_2011__45_3_331_0,
     author = {Cerioli, Marcia R. and Faria, Luerbio and Ferreira, Talita O. and Protti, F\'abio},
     title = {A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {331--346},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {3},
     year = {2011},
     doi = {10.1051/ita/2011106},
     mrnumber = {2836493},
     zbl = {1228.05224},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2011106/}
}
TY  - JOUR
AU  - Cerioli, Marcia R.
AU  - Faria, Luerbio
AU  - Ferreira, Talita O.
AU  - Protti, Fábio
TI  - A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 331
EP  - 346
VL  - 45
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2011106/
DO  - 10.1051/ita/2011106
LA  - en
ID  - ITA_2011__45_3_331_0
ER  - 
%0 Journal Article
%A Cerioli, Marcia R.
%A Faria, Luerbio
%A Ferreira, Talita O.
%A Protti, Fábio
%T A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 331-346
%V 45
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2011106/
%R 10.1051/ita/2011106
%G en
%F ITA_2011__45_3_331_0
Cerioli, Marcia R.; Faria, Luerbio; Ferreira, Talita O.; Protti, Fábio. A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 3, pp. 331-346. doi : 10.1051/ita/2011106. http://archive.numdam.org/articles/10.1051/ita/2011106/

[1] B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41 (1994) 153-180. | MR | Zbl

[2] P. Berman, M. Karpinski and A.D. Scott, Approximation hardness and satisfiability of bounded occurrence instances of SAT, in Electronic Colloquium on Computational Complexity - ECCC (2003).

[3] H. Breu, Algorithmic Aspects of Constrained Unit Disk Graphs. Ph.D. thesis, University of British Columbia (1996).

[4] H. Breu and D.G. Kirkpatrick, Unit disk graph recognition is NP-hard. Computational Geometry 9 (1998) 3-24. | MR | Zbl

[5] A. Borodin, I. Ivan, Y. Ye and B. Zimny, On sum coloring and sum multi-coloring for restricted families of graphs. Manuscript available at http://www.cs.toronto.edu/~bor/2420f10/stacs.pdf consulted 30 July 2011. | MR | Zbl

[6] B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs. Discrete Math. 86 (1990) 165-177. | MR | Zbl

[7] M.R. Cerioli, L. Faria, T.O. Ferreira and F. Protti, On minimum clique partition and maximum independent set in unit disk graphs and penny graphs: complexity and approximation. LACGA'2004 - Latin-American Conference on Combinatorics, Graphs and Applications. Santiago, Chile (2004). Electron. Notes Discrete Math. 18 (2004) 73-79. | MR | Zbl

[8] T. Erlebach, K. Jansen and E. Seidel, Polynomial-time approximation schemes for geometric graphs, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (2000) 671-679. | MR | Zbl

[9] P. Erdös, On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser. 103 (1975) 99-108. | MR | Zbl

[10] D. Lichtenstein, Planar formulae and their uses. SIAM J. Comput. 43 (1982) 329-393. | MR | Zbl

[11] M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977) 826-834. | MR | Zbl

[12] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979). | MR | Zbl

[13] M.C. Golumbic, The complexity of comparability graph recognition and coloring. Computing 18 (1977) 199-208. | MR | Zbl

[14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). | MR | Zbl

[15] H. Harborth, Lösung zu problem 664a. Elem. Math. 29 (1974) 14-15. | MR

[16] H.B. Hunt Iii, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns, NC-Approximation schemes for NP- and PSPACE-Hard problems for geometric graphs. J. Algor. 26 (1998) 238-274. | MR | Zbl

[17] K. Jansen and H. Müller, The minimum broadcast time problem for several processor networks. Theor. Comput. Sci. 147 (1995) 69-85. | MR | Zbl

[18] M.V. Marathe, H. Breu, H.B. Hunt Iii, S.S. Ravi and D.J. Rosenkrantz, Simple heuristics for unit disk Graphs. Networks 25 (1995) 59-68. | MR | Zbl

[19] T. Matsui, Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In Discrete and Computational Geometry. Lect. Notes Comput. Sci. 1763 (2000) 194-200. | MR | Zbl

[20] I.A. Pirwani and M.R. Salavatipour, A weakly robust PTAS for minimum clique partition in unit disk graphs (Extended Abstract), Proceedings of SWAT 2010. Lect. Notes Comput. Sci. 6139 (2010) 188-199. | MR | Zbl

[21] S.V. Pemmaraju and I.A. Pirwani, Good quality virtual realization of unit ball graphs, Proceedings of the 15th Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 4698 (2007) 311-322. | Zbl

[22] O. Reutter, Problem 664a. Elem. Math. 27 (1972) 19.

[23] J.P. Spinrad, Efficient Graph Representations, Fields Institute Monographs 19. American Mathematical Society (2003). | MR | Zbl

[24] L.G. Valiant, Universality considerations in VLSI circuits. IEEE Trans. Comput. 30 (1981) 135-140. | MR | Zbl

Cité par Sources :