# A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Marcia R. Cerioli; Luerbio Faria; Talita O. Ferreira; Fábio Protti

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

- Volume: 45, Issue: 3, page 331-346
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCerioli, Marcia R., et al. "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 45.3 (2011): 331-346. <http://eudml.org/doc/273035>.

@article{Cerioli2011,

abstract = {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.},

author = {Cerioli, Marcia R., Faria, Luerbio, Ferreira, Talita O., Protti, Fábio},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {unit disk graphs; unit coin graphs; penny graphs; independent set; clique partition; approximation algorithms},

language = {eng},

number = {3},

pages = {331-346},

publisher = {EDP-Sciences},

title = {A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation},

url = {http://eudml.org/doc/273035},

volume = {45},

year = {2011},

}

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

PB - EDP-Sciences

VL - 45

IS - 3

SP - 331

EP - 346

AB - 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.

LA - eng

KW - unit disk graphs; unit coin graphs; penny graphs; independent set; clique partition; approximation algorithms

UR - http://eudml.org/doc/273035

ER -

## References

top- [1] B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs. J. ACM41 (1994) 153–180. Zbl0807.68067MR1369197
- [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 Geometry9 (1998) 3–24. Zbl0894.68099MR1492799
- [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. Zbl1232.68061MR2885875
- [6] B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs. Discrete Math.86 (1990) 165–177. Zbl0739.05079MR1088569
- [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. Zbl1075.05571MR2162916
- [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. Zbl0988.65020MR1958541
- [9] P. Erdös, On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser.103 (1975) 99–108. Zbl0303.52006MR411984
- [10] D. Lichtenstein, Planar formulae and their uses. SIAM J. Comput.43 (1982) 329–393. Zbl0478.68043MR652906
- [11] M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math.32 (1977) 826–834. Zbl0396.05009MR443426
- [12] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979). Zbl0411.68039MR519066
- [13] M.C. Golumbic, The complexity of comparability graph recognition and coloring. Computing18 (1977) 199–208. Zbl0365.05025MR502231
- [14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). Zbl0541.05054MR562306
- [15] H. Harborth, Lösung zu problem 664a. Elem. Math.29 (1974) 14–15. MR354389
- [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. Zbl0894.68105MR1606504
- [17] K. Jansen and H. Müller, The minimum broadcast time problem for several processor networks. Theor. Comput. Sci.147 (1995) 69–85. Zbl0873.68009MR1346097
- [18] M.V. Marathe, H. Breu, H.B. Hunt III, S.S. Ravi and D.J. Rosenkrantz, Simple heuristics for unit disk Graphs. Networks25 (1995) 59–68. Zbl0821.90128MR1321110
- [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. Zbl0955.05100MR1787526
- [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. Zbl1284.05220MR2678497
- [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. Zbl1151.05333
- [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). Zbl1033.05001MR1971502
- [24] L.G. Valiant, Universality considerations in VLSI circuits. IEEE Trans. Comput.30 (1981) 135–140. Zbl0455.94046MR605722

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.