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

Abstract

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

How to cite

top

Cerioli, 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
  1. B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs. J. ACM41 (1994) 153–180.  
  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.  
  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 consulted 30 July 2011.  URIhttp://www.cs.toronto.edu/~bor/2420f10/stacs.pdf
  6. B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs. Discrete Math.86 (1990) 165–177.  
  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.  
  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.  
  9. P. Erdös, On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser.103 (1975) 99–108.  
  10. D. Lichtenstein, Planar formulae and their uses. SIAM J. Comput.43 (1982) 329–393.  
  11. M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math.32 (1977) 826–834.  
  12. M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979).  
  13. M.C. Golumbic, The complexity of comparability graph recognition and coloring. Computing18 (1977) 199–208.  
  14. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980).  
  15. H. Harborth, Lösung zu problem 664a. Elem. Math.29 (1974) 14–15.  
  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.  
  17. K. Jansen and H. Müller, The minimum broadcast time problem for several processor networks. Theor. Comput. Sci.147 (1995) 69–85.  
  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.  
  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.  
  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.  
  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.  
  22. O. Reutter, Problem 664a. Elem. Math.27 (1972) 19.  
  23. J.P. Spinrad, Efficient Graph Representations, Fields Institute Monographs19. American Mathematical Society (2003).  
  24. L.G. Valiant, Universality considerations in VLSI circuits. IEEE Trans. Comput.30 (1981) 135–140.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.