Document Open Access Logo

5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size

Authors Bart M. P. Jansen , Jari J. H. de Kroon , Michał Włodarczyk

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.66.pdf
  • Filesize: 0.94 MB
  • 16 pages

Document Identifiers

Author Details

Bart M. P. Jansen
  • Eindhoven University of Technology, The Netherlands
Jari J. H. de Kroon
  • Eindhoven University of Technology, The Netherlands
Michał Włodarczyk
  • University of Warsaw, Poland

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch).

Cite AsGet BibTex

Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. 5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 66:1-66:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.66

Abstract

The notion of ℋ-treewidth, where ℋ is a hereditary graph class, was recently introduced as a generalization of the treewidth of an undirected graph. Roughly speaking, a graph of ℋ-treewidth at most k can be decomposed into (arbitrarily large) ℋ-subgraphs which interact only through vertex sets of size 𝒪(k) which can be organized in a tree-like fashion. ℋ-treewidth can be used as a hybrid parameterization to develop fixed-parameter tractable algorithms for ℋ-deletion problems, which ask to find a minimum vertex set whose removal from a given graph G turns it into a member of ℋ. The bottleneck in the current parameterized algorithms lies in the computation of suitable tree ℋ-decompositions. We present FPT-approximation algorithms to compute tree ℋ-decompositions for hereditary and union-closed graph classes ℋ. Given a graph of ℋ-treewidth k, we can compute a 5-approximate tree ℋ-decomposition in time f(𝒪(k)) ⋅ n^𝒪(1) whenever ℋ-deletion parameterized by solution size can be solved in time f(k) ⋅ n^𝒪(1) for some function f(k) ≥ 2^k. The current-best algorithms either achieve an approximation factor of k^𝒪(1) or construct optimal decompositions while suffering from non-uniformity with unknown parameter dependence. Using these decompositions, we obtain algorithms solving Odd Cycle Transversal in time 2^𝒪(k) ⋅ n^𝒪(1) parameterized by bipartite-treewidth and Vertex Planarization in time 2^𝒪(k log k) ⋅ n^𝒪(1) parameterized by planar-treewidth, showing that these can be as fast as the solution-size parameterizations and giving the first ETH-tight algorithms for parameterizations by hybrid width measures.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • fixed-parameter tractability
  • treewidth
  • graph decompositions

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9-12, 2022, pages 1976-2004. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.79.
  2. Akanksha Agrawal and M. S. Ramanujan. Distance from triviality 2.0: Hybrid parameterizations. In Cristina Bazgan and Henning Fernau, editors, Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings, volume 13270 of Lecture Notes in Computer Science, pages 3-20. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-06678-8_1.
  3. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods, 8(2):277-284, 1987. URL: https://doi.org/10.1137/0608024.
  4. Mahdi Belbasi and Martin Fürer. An improvement of reed’s treewidth approximation. J. Graph Algorithms Appl., 26(2):257-282, 2022. URL: https://doi.org/10.7155/jgaa.00593.
  5. Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree-decompositions. Comb. Probab. Comput., 11(6):541-547, 2002. URL: https://doi.org/10.1017/S0963548302005369.
  6. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: https://doi.org/10.1137/S0097539793251219.
  7. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1-45, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00228-4.
  8. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  9. Hans L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996. URL: https://doi.org/10.1006/jagm.1996.0049.
  10. Hans L. Bodlaender and Arie M. C. A. Koster. Treewidth computations I. Upper bounds. Inf. Comput., 208(3):259-275, 2010. URL: https://doi.org/10.1016/j.ic.2009.03.008.
  11. Hans L. Bodlaender and Arie M. C. A. Koster. Treewidth computations II. Lower bounds. Inf. Comput., 209(7):1103-1119, 2011. URL: https://doi.org/10.1016/j.ic.2011.04.003.
  12. Jannis Bulian and Anuj Dawar. Graph isomorphism parameterized by elimination distance to bounded degree. Algorithmica, 75(2):363-382, 2016. URL: https://doi.org/10.1007/s00453-015-0045-3.
  13. Jannis Bulian and Anuj Dawar. Fixed-parameter tractable distances to sparse graph classes. Algorithmica, 79(1):139-158, 2017. URL: https://doi.org/10.1007/s00453-016-0235-7.
  14. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.026.
  15. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. URL: https://doi.org/10.1017/CBO9780511977619.
  16. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  17. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The first parameterized algorithms and computational experiments challenge. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 30:1-30:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.IPEC.2016.30.
  18. Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1-30:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.30.
  19. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  20. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  21. Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what matters: A hybrid approach to dynamic programming with treewidth. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 42:1-42:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.42.
  22. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, and Yngve Villanger. Local search: Is brute-force avoidable? J. Comput. Syst. Sci., 78(3):707-719, 2012. URL: https://doi.org/10.1016/j.jcss.2011.10.003.
  23. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  24. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Clique-width: on the price of generality. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 825-834. SIAM, 2009. URL: https://doi.org/10.1137/1.9781611973068.90.
  25. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM J. Comput., 39(5):1941-1956, 2010. URL: https://doi.org/10.1137/080742270.
  26. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput., 43(5):1541-1563, 2014. URL: https://doi.org/10.1137/130910932.
  27. Jiong Guo, Sepp Hartung, Rolf Niedermeier, and Ondrej Suchý. The parameterized complexity of local search for TSP, more refined. Algorithmica, 67(1):89-110, 2013. URL: https://doi.org/10.1007/s00453-012-9685-8.
  28. Jiong Guo, Danny Hermelin, and Christian Komusiewicz. Local search for string problems: Brute-force is essentially optimal. Theor. Comput. Sci., 525:30-41, 2014. URL: https://doi.org/10.1016/j.tcs.2013.05.006.
  29. Bart M. P. Jansen and Jari J. H. de Kroon. FPT algorithms to compute the elimination distance to bipartite graphs and more. In Lukasz Kowalik, Michal Pilipczuk, and Pawel Rzazewski, editors, Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, Revised Selected Papers, volume 12911 of Lecture Notes in Computer Science, pages 80-93. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-86838-3_6.
  30. Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. Vertex deletion parameterized by elimination distance and even less. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 1757-1769, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451068.
  31. Bart M. P. Jansen, Jari J. H. de Kroon, and Michal Włodarczyk. 5-approximation for H-treewidth essentially as fast as H-deletion parameterized by solution size. CoRR, abs/2306.17065, 2023. URL: https://arxiv.org/abs/2306.17065.
  32. Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. Vertex deletion parameterized by elimination distance and even less. CoRR, abs/2105.04660, 2021. URL: https://arxiv.org/abs/2105.04660.
  33. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1802-1811. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.130.
  34. Ken-ichi Kawarabayashi. Planarity allowing few error vertices in linear time. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 639-648. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.45.
  35. Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 184-192. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00026.
  36. Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. CoRR, abs/2211.07154, 2022. URL: https://doi.org/10.48550/arXiv.2211.07154.
  37. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. URL: https://doi.org/10.1145/3170442.
  38. Dániel Marx. Four shorts stories on surprising algorithmic uses of treewidth. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 129-144. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-42071-0_10.
  39. Dániel Marx and Ildikó Schlotter. Obtaining a planar graph by vertex deletion. Algorithmica, 62(3-4):807-822, 2012. URL: https://doi.org/10.1007/s00453-010-9484-z.
  40. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  41. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B, 96(4):514-528, 2006. URL: https://doi.org/10.1016/j.jctb.2005.10.006.
  42. Marcin Pilipczuk. A tight lower bound for vertex planarization on graphs of bounded treewidth. Discret. Appl. Math., 231:211-216, 2017. URL: https://doi.org/10.1016/j.dam.2016.05.019.
  43. Bruce A. Reed. Finding approximate separators and computing tree width quickly. In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 221-228. ACM, 1992. URL: https://doi.org/10.1145/129712.129734.
  44. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004. URL: https://doi.org/10.1016/j.orl.2003.10.009.
  45. N. Robertson and P.D. Seymour. Graph minors XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  46. Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986. URL: https://doi.org/10.1016/0196-6774(86)90023-4.
  47. Neil Robertson and Paul D. Seymour. Graph minors. IV. Tree-width and well-quasi-ordering. J. Comb. Theory, Ser. B, 48(2):227-254, 1990. URL: https://doi.org/10.1016/0095-8956(90)90120-O.
  48. Toshiki Saitoh, Ryo Yoshinaka, and Hans L. Bodlaender. Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes. In Ryuhei Uehara, Seok-Hee Hong, and Subhas C. Nandy, editors, WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 - March 2, 2021, Proceedings, volume 12635 of Lecture Notes in Computer Science, pages 142-153. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-68211-8_12.
  49. A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003. 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 Imprint Privacy Contact