Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs

Authors Esther Galby, Andrea Munaro , Shizhou Yang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.34.pdf
  • Filesize: 0.82 MB
  • 15 pages

Document Identifiers

Author Details

Esther Galby
  • Institute for Algorithms and Complexity, Technische Universität Hamburg, Germany
Andrea Munaro
  • Department of Mathematical, Physical and Computer Sciences, University of Parma, Italy
Shizhou Yang
  • School of Mathematics and Physics, Queen’s University Belfast, UK

Acknowledgements

We thank the anonymous reviewers for valuable comments.

Cite As Get BibTex

Esther Galby, Andrea Munaro, and Shizhou Yang. Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.34

Abstract

We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Independent packings
  • intersection graphs
  • polynomial-time approximation schemes
  • tree-independence number

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K. Agarwal, Marc van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles. Computational Geometry, 11(3):209-218, 1998. Google Scholar
  2. Jochen Alber and Jiří Fiala. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. Journal of Algorithms, 52(2):134-151, 2004. Google Scholar
  3. Andrei Asinowski, Elad Cohen, Martin Charles Golumbic, Vincent Limouzy, Marina Lipshteyn, and Michal Stern. Vertex intersection graphs of paths on a grid. Journal of Graph Algorithms and Applications, 16(2):129-150, 2012. Google Scholar
  4. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41(1):153-180, 1994. Google Scholar
  5. Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue. True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry (SoCG 2022), volume 224 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1-11:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  6. Stephane Bessy, Marin Bougeret, Steven Chaplick, Daniel Gonçalves, and Christophe Paul. On independent set in B₁-EPG graphs. Discrete Applied Mathematics, 278:62-72, 2020. Google Scholar
  7. Therese Biedl and Martin Derka. Splitting B₂-VPG graphs into outer-string and co-comparability graphs. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures - 15th International Symposium, (WADS 2017), volume 10389 of Lecture Notes in Computer Science, pages 157-168. Springer, 2017. Google Scholar
  8. Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, and Stéphan Thomassé. EPTAS and subexponential algorithm for maximum clique on disk and unit ball graphs. J. ACM, 68(2), 2021. Google Scholar
  9. Flavia Bonomo-Braberman and Carolina Lucía Gonzalez. A new approach on locally checkable problems. Discrete Applied Mathematics, 314:53-80, June 2022. Google Scholar
  10. Kathie Cameron and Pavol Hell. Independent packings in structured graphs. Mathematical Programming, 105(2-3):201-213, 2006. Google Scholar
  11. Timothy M Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003. Google Scholar
  12. Timothy M. Chan. A note on maximum independent sets in rectangle intersection graphs. Information Processing Letters, 89(1):19-23, 2004. Google Scholar
  13. L.Sunil Chandran and C.R. Subramanian. Girth and treewidth. Journal of Combinatorial Theory, Series B, 93(1):23-32, 2005. Google Scholar
  14. Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing tree decompositions with small independence number. CoRR, abs/2207.09993, 2022. URL: https://arxiv.org/abs/2207.09993.
  15. Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. II. Tree-independence number. CoRR, abs/2111.04543, 2022. URL: https://arxiv.org/abs/2111.04543.
  16. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM Journal on Computing, 49(6):1291-1331, 2020. Google Scholar
  17. Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pages 637-646. IEEE Computer Society, 2005. Google Scholar
  18. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar. Approximation algorithms via contraction decomposition. Combinatorica, 30(5):533-552, 2010. Google Scholar
  19. Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. Journal of Combinatorial Theory, Series B, 91(1):25-41, 2004. Google Scholar
  20. Vida Dujmović, David Eppstein, and David R. Wood. Structure of graphs with locally restricted crossings. SIAM Journal on Discrete Mathematics, 31(2):805-824, 2017. Google Scholar
  21. Vida Dujmović, Pat Morin, and David R. Wood. Layered separators in minor-closed graph classes with applications. Journal of Combinatorial Theory, Series B, 127:111-147, 2017. Google Scholar
  22. Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood. Clustered 3-colouring graphs of bounded degree. Combinatorics, Probability and Computing, 31(1):123-135, 2022. Google Scholar
  23. Vida Dujmović, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. CoRR, abs/1907.05168, 2022. URL: https://arxiv.org/abs/1907.05168.
  24. Zdeněk Dvořák. Sublinear separators, fragility and subexponential expansion. European Journal of Combinatorics, 52:103-119, 2016. Google Scholar
  25. Zdeněk Dvořák. Talk at GWP 2022 - satellite workshop of ICALP 2022, 2022. URL: https://homepages.ecs.vuw.ac.nz/~bretteni/GWP2022/.
  26. Zdeněk Dvořák. Approximation Metatheorems for Classes with Bounded Expansion. In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), volume 227 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  27. Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On comparable box dimension. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry (SoCG 2022), volume 224 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  28. Zdeněk Dvořák and Abhiruk Lahiri. Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1-40:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  29. David Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27(3):275-291, 2000. Google Scholar
  30. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34(6):1302-1323, 2005. Google Scholar
  31. Hiroshi Eto, Fengrui Guo, and Eiji Miyano. Distance-d independent set problems for bipartite and chordal graphs. Journal of Combinatorial Optimization, 27(1):88-99, 2014. Google Scholar
  32. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In Yuval Rabani, editor, Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1563-1575. SIAM, 2012. Google Scholar
  33. Jacob Fox and János Pach. Computing the independence number of intersection graphs. In Dana Randall, editor, Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pages 1161-1165. SIAM, 2011. Google Scholar
  34. Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy Pittu, and Andreas Wiese. A 3-approximation algorithm for Maximum Independent Set of rectangles. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 894-905. SIAM, 2022. Google Scholar
  35. Matt Gibson and Imran A. Pirwani. Algorithms for dominating set in disk graphs: Breaking the log n barrier. In Mark de Berg and Ulrich Meyer, editors, Algorithms - ESA 2010, volume 6346 of Lecture Notes in Computer Science, pages 243-254. Springer Berlin Heidelberg, 2010. Google Scholar
  36. Martin Charles Golumbic, Marina Lipshteyn, and Michal Stern. Edge intersection graphs of single bend paths on a grid. Networks, 54(3):130-138, 2009. Google Scholar
  37. Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 49(1):1-11, 2007. Google Scholar
  38. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130-136, 1985. Google Scholar
  39. Harry B Hunt, Madhav V Marathe, Venkatesh Radhakrishnan, S.S Ravi, Daniel J Rosenkrantz, and Richard E Stearns. NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms, 26(2):238-274, 1998. Google Scholar
  40. Abhiruk Lahiri, Joydeep Mukherjee, and C. R. Subramanian. Maximum Independent Set on B₁-VPG graphs. In Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, and Ding-Zhu Du, editors, Combinatorial Optimization and Applications - 9th International Conference (COCOA 2015), volume 9486 of Lecture Notes in Computer Science, pages 633-646. Springer, 2015. Google Scholar
  41. Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. A framework for approximation schemes on disk graphs. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 2228-2241. SIAM, 2023. Google Scholar
  42. Dániel Marx. Efficient approximation schemes for geometric problems? In Gerth Stølting Brodal and Stefano Leonardi, editors, Algorithms - ESA 2005, volume 3669 of Lecture Notes in Computer Science, pages 448-459. Springer Berlin Heidelberg, 2005. Google Scholar
  43. Tomomi Matsui. Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In Jin Akiyama, Mikio Kano, and Masatsugu Urabe, editors, Discrete and Computational Geometry, pages 194-200. Springer Berlin Heidelberg, 1998. Google Scholar
  44. Saeed Mehrabi. Approximating domination on intersection graphs of paths on a grid. In Roberto Solis-Oba and Rudolf Fleischer, editors, Approximation and Online Algorithms - 15th International Workshop (WAOA 2017), volume 10787 of Lecture Notes in Computer Science, pages 76-89. Springer, 2017. Google Scholar
  45. Martin Milanič and Paweł Rza̧żewski. Tree decompositions with bounded independence number: beyond independent sets. CoRR, abs/2209.12315, 2022. URL: https://arxiv.org/abs/2209.12315.
  46. Tim Nieberg, Johann L. Hurink, and Walter Kern. A robust PTAS for maximum weight independent sets in unit disk graphs. In Juraj Hromkovic, Manfred Nagl, and Bernhard Westfechtel, editors, Graph-Theoretic Concepts in Computer Science, 30th International Workshop (WG 2004), volume 3353 of Lecture Notes in Computer Science, pages 214-221. Springer, 2004. Google Scholar
  47. Yury Orlovich, Alexandre Dolgui, Gerd Finke, Valery Gordon, and Frank Werner. The complexity of dissociation set problems in graphs. Discrete Applied Mathematics, 159(13):1352-1366, 2011. Google Scholar
  48. Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 1035-1054. SIAM, 2019. Google Scholar
  49. Erik Jan van Leeuwen. Approximation algorithms for unit disk graphs. In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, 31st International Workshop (WG 2005), volume 3787 of Lecture Notes in Computer Science, pages 351-361. Springer, 2005. Google Scholar
  50. Erik Jan van Leeuwen. Better approximation schemes for disk graphs. In Lars Arge and Rusins Freivalds, editors, Algorithm Theory - SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, volume 4059 of Lecture Notes in Computer Science, pages 316-327. Springer, 2006. Google Scholar
  51. Mihalis Yannakakis. Node-deletion problems on bipartite graphs. SIAM Journal on Computing, 10(2):310-327, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact