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.
@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},
volume = {45},
year = {2011},
pages = {331-346},
doi = {10.1051/ita/2011106},
mrnumber = {2836493},
zbl = {1228.05224},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 331-346. doi : 10.1051/ita/2011106. http://gdmltest.u-ga.fr/item/ITA_2011__45_3_331_0/
[1] , Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41 (1994) 153-180. | MR 1369197 | Zbl 0807.68067
[2] , and , Approximation hardness and satisfiability of bounded occurrence instances of SAT, in Electronic Colloquium on Computational Complexity - ECCC (2003).
[3] , Algorithmic Aspects of Constrained Unit Disk Graphs. Ph.D. thesis, University of British Columbia (1996).
[4] and , Unit disk graph recognition is NP-hard. Computational Geometry 9 (1998) 3-24. | MR 1492799 | Zbl 0894.68099
[5] , , and , 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 2885875 | Zbl 1232.68061
[6] , and , Unit disk graphs. Discrete Math. 86 (1990) 165-177. | MR 1088569 | Zbl 0739.05079
[7] , , and , 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 2162916 | Zbl 1075.05571
[8] , and , Polynomial-time approximation schemes for geometric graphs, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (2000) 671-679. | MR 1958541 | Zbl 0988.65020
[9] , On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser. 103 (1975) 99-108. | MR 411984 | Zbl 0303.52006
[10] , Planar formulae and their uses. SIAM J. Comput. 43 (1982) 329-393. | MR 652906 | Zbl 0478.68043
[11] and , The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977) 826-834. | MR 443426 | Zbl 0396.05009
[12] and , Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979). | MR 519066 | Zbl 0411.68039
[13] , The complexity of comparability graph recognition and coloring. Computing 18 (1977) 199-208. | MR 502231 | Zbl 0365.05025
[14] , Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). | MR 562306 | Zbl 0541.05054
[15] , Lösung zu problem 664a. Elem. Math. 29 (1974) 14-15. | MR 354389
[16] , , , , and , NC-Approximation schemes for NP- and PSPACE-Hard problems for geometric graphs. J. Algor. 26 (1998) 238-274. | MR 1606504 | Zbl 0894.68105
[17] and , The minimum broadcast time problem for several processor networks. Theor. Comput. Sci. 147 (1995) 69-85. | MR 1346097 | Zbl 0873.68009
[18] , , , and , Simple heuristics for unit disk Graphs. Networks 25 (1995) 59-68. | MR 1321110 | Zbl 0821.90128
[19] , 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 1787526 | Zbl 0955.05100
[20] and , 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 2678497 | Zbl 1284.05220
[21] and , 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 1151.05333
[22] , Problem 664a. Elem. Math. 27 (1972) 19.
[23] , Efficient Graph Representations, Fields Institute Monographs 19. American Mathematical Society (2003). | MR 1971502 | Zbl 1033.05001
[24] , Universality considerations in VLSI circuits. IEEE Trans. Comput. 30 (1981) 135-140. | MR 605722 | Zbl 0455.94046