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

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 - 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. [1] B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs. J. ACM41 (1994) 153–180. Zbl0807.68067MR1369197
  2. [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. [3] H. Breu, Algorithmic Aspects of Constrained Unit Disk Graphs. Ph.D. thesis, University of British Columbia (1996). 
  4. [4] H. Breu and D.G. Kirkpatrick, Unit disk graph recognition is NP-hard. Computational Geometry9 (1998) 3–24. Zbl0894.68099MR1492799
  5. [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. [6] B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs. Discrete Math.86 (1990) 165–177. Zbl0739.05079MR1088569
  7. [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. [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. [9] P. Erdös, On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser.103 (1975) 99–108. Zbl0303.52006MR411984
  10. [10] D. Lichtenstein, Planar formulae and their uses. SIAM J. Comput.43 (1982) 329–393. Zbl0478.68043MR652906
  11. [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. [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. [13] M.C. Golumbic, The complexity of comparability graph recognition and coloring. Computing18 (1977) 199–208. Zbl0365.05025MR502231
  14. [14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). Zbl0541.05054MR562306
  15. [15] H. Harborth, Lösung zu problem 664a. Elem. Math.29 (1974) 14–15. MR354389
  16. [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. [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. [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. [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. [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. [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. [22] O. Reutter, Problem 664a. Elem. Math. 27 (1972) 19. 
  23. [23] J.P. Spinrad, Efficient Graph Representations, Fields Institute Monographs 19. American Mathematical Society (2003). Zbl1033.05001MR1971502
  24. [24] L.G. Valiant, Universality considerations in VLSI circuits. IEEE Trans. Comput.30 (1981) 135–140. Zbl0455.94046MR605722

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.