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) no. 3, pp. 331-346.

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.

DOI : 10.1051/ita/2011106
Classification : 05C69, 05C75, 68W25, 68Q25
Mots-clés : unit disk graphs, unit coin graphs, penny graphs, independent set, clique partition, approximation algorithms 
@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},
     pages = {331--346},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {3},
     year = {2011},
     doi = {10.1051/ita/2011106},
     mrnumber = {2836493},
     zbl = {1228.05224},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011106/}
}
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
SP  - 331
EP  - 346
VL  - 45
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011106/
DO  - 10.1051/ita/2011106
LA  - en
ID  - ITA_2011__45_3_331_0
ER  - 
%0 Journal Article
%A Cerioli, Marcia R.
%A Faria, Luerbio
%A Ferreira, Talita O.
%A Protti, Fábio
%T A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 331-346
%V 45
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011106/
%R 10.1051/ita/2011106
%G en
%F 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) no. 3, pp. 331-346. doi : 10.1051/ita/2011106. http://www.numdam.org/articles/10.1051/ita/2011106/

[1] B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41 (1994) 153-180. | MR | Zbl

[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 Geometry 9 (1998) 3-24. | MR | Zbl

[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. | MR | Zbl

[6] B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs. Discrete Math. 86 (1990) 165-177. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[9] P. Erdös, On some problems of elementary and combinatorial geometry. Ann. Math. Pura Appl. Ser. 103 (1975) 99-108. | MR | Zbl

[10] D. Lichtenstein, Planar formulae and their uses. SIAM J. Comput. 43 (1982) 329-393. | MR | Zbl

[11] M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977) 826-834. | MR | Zbl

[12] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979). | MR | Zbl

[13] M.C. Golumbic, The complexity of comparability graph recognition and coloring. Computing 18 (1977) 199-208. | MR | Zbl

[14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). | MR | Zbl

[15] H. Harborth, Lösung zu problem 664a. Elem. Math. 29 (1974) 14-15. | MR

[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. | MR | Zbl

[17] K. Jansen and H. Müller, The minimum broadcast time problem for several processor networks. Theor. Comput. Sci. 147 (1995) 69-85. | MR | Zbl

[18] M.V. Marathe, H. Breu, H.B. Hunt Iii, S.S. Ravi and D.J. Rosenkrantz, Simple heuristics for unit disk Graphs. Networks 25 (1995) 59-68. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[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. | Zbl

[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). | MR | Zbl

[24] L.G. Valiant, Universality considerations in VLSI circuits. IEEE Trans. Comput. 30 (1981) 135-140. | MR | Zbl

  • Maehara, Hiroshi; Martini, Horst Graphs and Circle-Systems, Circles, Spheres and Spherical Geometry (2024), p. 49 | DOI:10.1007/978-3-031-62776-7_3
  • Han, Xiaoyu; Xiong, Haoran; He, Zhenying; Wang, Peng; Wang, Chen; Wang, X. Sean Akane: Perplexity-Guided Time Series Data Cleaning, Proceedings of the ACM on Management of Data, Volume 2 (2024) no. 3, p. 1 | DOI:10.1145/3654993
  • Dondi, Riccardo; Lafond, Manuel On the tractability of covering a graph with 2-clubs, Algorithmica, Volume 85 (2023) no. 4, pp. 992-1028 | DOI:10.1007/s00453-022-01062-3 | Zbl:7673393
  • Bhore, Sujoy; Jain, Rahul Space-efficient algorithms for reachability in directed geometric graphs, Theoretical Computer Science, Volume 961 (2023), p. 13 (Id/No 113938) | DOI:10.1016/j.tcs.2023.113938 | Zbl:7688228
  • He, Zunwu; Hua, Bobo Harmonic functions of polynomial growth on infinite penny graphs, Journal of the London Mathematical Society. Second Series, Volume 105 (2022) no. 1, pp. 565-586 | DOI:10.1112/jlms.12529 | Zbl:1519.05181
  • Adamson, Duncan; Deligkas, Argyrios; Gusev, Vladimir; Potapov, Igor On the hardness of energy minimisation for crystal structure prediction, Fundamenta Informaticae, Volume 184 (2021) no. 3, pp. 181-203 | DOI:10.3233/fi-2021-2096 | Zbl:1515.82140
  • Hua, Bobo Discrete harmonic functions on infinite penny graphs, Vietnam Journal of Mathematics, Volume 49 (2021) no. 2, pp. 461-472 | DOI:10.1007/s10013-020-00471-7 | Zbl:1469.05045
  • Adamson, Duncan; Deligkas, Argyrios; Gusev, Vladimir V.; Potapov, Igor On the hardness of energy minimisation for crystal structure prediction, SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings, Cham: Springer, 2020, pp. 587-596 | DOI:10.1007/978-3-030-38919-2_48 | Zbl:1440.82010
  • Dondi, Riccardo; Lafond, Manuel On the tractability of covering a graph with 2-clubs, Fundamentals of computation theory. 22nd international symposium, FCT 2019, Copenhagen, Denmark, August 12–14, 2019. Proceedings, Cham: Springer, 2019, pp. 243-257 | DOI:10.1007/978-3-030-25027-0_17 | Zbl:1534.68158
  • Chaplick, Steven; Förster, Henry; Kryven, Myroslav; Wolff, Alexander On arrangements of orthogonal circles, Graph drawing and network visualization. 27th international symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019. Proceedings, Cham: Springer, 2019, pp. 216-229 | DOI:10.1007/978-3-030-35802-0_17 | Zbl:1542.68132
  • Dondi, Riccardo; Mauri, Giancarlo; Sikora, Florian; Zoppis, Italo Covering a graph with clubs, Journal of Graph Algorithms and Applications, Volume 23 (2019) no. 2, pp. 271-292 | DOI:10.7155/jgaa.00491 | Zbl:1411.05216
  • Dondi, Riccardo; Mauri, Giancarlo; Sikora, Florian; Zoppis, Italo Covering with Clubs: Complexity and Approximability, Combinatorial Algorithms, Volume 10979 (2018), p. 153 | DOI:10.1007/978-3-319-94667-2_13

Cité par 12 documents. Sources : Crossref, zbMATH