# 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 (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 45.3 (2011): 331-346. <http://eudml.org/doc/221997>.

@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},

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

language = {eng},

month = {9},

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/221997},

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

DA - 2011/9//

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; unit disk graphs; clique partition

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

ER -

## References

top- B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs. J. ACM41 (1994) 153–180. Zbl0807.68067
- 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).
- H. Breu, Algorithmic Aspects of Constrained Unit Disk Graphs. Ph.D. thesis, University of British Columbia (1996).
- H. Breu and D.G. Kirkpatrick, Unit disk graph recognition is NP-hard. Computational Geometry9 (1998) 3–24. Zbl0894.68099
- A. Borodin, I. Ivan, Y. Ye and B. Zimny, On sum coloring and sum multi-coloring for restricted families of graphs. Manuscript available at consulted 30 July 2011. Zbl1232.68061URIhttp://www.cs.toronto.edu/~bor/2420f10/stacs.pdf
- B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs. Discrete Math.86 (1990) 165–177. Zbl0739.05079
- 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.05571
- 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.65020
- P. Erdös, On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser.103 (1975) 99–108. Zbl0303.52006
- D. Lichtenstein, Planar formulae and their uses. SIAM J. Comput.43 (1982) 329–393. Zbl0478.68043
- M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math.32 (1977) 826–834. Zbl0396.05009
- M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979). Zbl0411.68039
- M.C. Golumbic, The complexity of comparability graph recognition and coloring. Computing18 (1977) 199–208. Zbl0365.05025
- M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). Zbl0541.05054
- H. Harborth, Lösung zu problem 664a. Elem. Math.29 (1974) 14–15.
- 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.68105
- K. Jansen and H. Müller, The minimum broadcast time problem for several processor networks. Theor. Comput. Sci.147 (1995) 69–85. Zbl0873.68009
- 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.90128
- 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.05100
- 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.05220
- 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
- O. Reutter, Problem 664a. Elem. Math.27 (1972) 19.
- J.P. Spinrad, Efficient Graph Representations, Fields Institute Monographs19. American Mathematical Society (2003).
- L.G. Valiant, Universality considerations in VLSI circuits. IEEE Trans. Comput.30 (1981) 135–140. Zbl0455.94046

## NotesEmbed ?

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