Document Open Access Logo

A Unifying Framework for Characterizing and Computing Width Measures

Authors Eduard Eiben , Robert Ganian , Thekla Hamm , Lars Jaffke , O-joung Kwon

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.63.pdf
  • Filesize: 0.92 MB
  • 23 pages

Document Identifiers

Author Details

Eduard Eiben
  • Department of Computer Science, Royal Holloway, University of London, Egham, UK
Robert Ganian
  • Algorithms and Complexity Group, TU Wien, Austria
Thekla Hamm
  • Algorithms and Complexity Group, TU Wien, Austria
Lars Jaffke
  • Department of Informatics, University of Bergen, Norway
O-joung Kwon
  • Department of Mathematics, Incheon National University, South Korea
  • Discrete Mathematics Group, Institute for Basic Science, Daejeon, South Korea

Funding

  • Ganian, Robert: Robert Ganian acknowledges support by the Austrian Science Fund (FWF, projects P31336 and Y1329).
  • Hamm, Thekla: Thekla Hamm acknowledges support by the Austrian Science Fund (FWF, projects P31336, Y1329 and W1255-N23).
  • Jaffke, Lars: Lars Jaffke acknowledges support by the Norwegian Research Council (NFR, project 274526).
  • Kwon, O-joung: O-joung Kwon was supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF- 2018R1D1A1B07050294), and by the Institute for Basic Science (IBS-R029-C1).

Cite As Get BibTex

Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon. A Unifying Framework for Characterizing and Computing Width Measures. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 63:1-63:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.63

Abstract

Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify ℱ-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of ℱ-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible ℱ-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • branchwidth
  • parameterized algorithms
  • mim-width
  • treewidth
  • clique-width

Metrics

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

Related Versions

References

  1. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci., 511:54-65, 2013. URL: https://doi.org/10.1016/j.tcs.2013.01.011.
  2. Benjamin Bergougnoux and Mamadou Moustapha Kanté. More applications of the d-neighbor equivalence: Acyclicity and connectivity constraints. SIAM J. Discret. Math., 35(3):1881-1926, 2021. URL: https://doi.org/10.1137/20M1350571.
  3. Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann. On bounded-degree vertex deletion parameterized by treewidth. Discret. Appl. Math., 160(1-2):53-60, 2012. Google Scholar
  4. 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. Google Scholar
  5. Hans L. Bodlaender, Lars Jaffke, and Jan Arne Telle. Typical sequences revisited - computing width parameters of graphs. In Christophe Paul and Markus Bläser, editors, Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, volume 154 of LIPIcs, pages 57:1-57:16. Schloss Dagstuhl, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.57.
  6. Hans L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996. Google Scholar
  7. Binh-Minh Bui-Xuan, Ondrej Suchý, Jan Arne Telle, and Martin Vatshelle. Feedback vertex set on graphs of low clique-width. Eur. J. Comb., 34(3):666-679, 2013. Google Scholar
  8. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discret. Appl. Math., 158(7):809-819, 2010. Google Scholar
  9. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci., 511:66-76, 2013. URL: https://doi.org/10.1016/j.tcs.2013.01.009.
  10. B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. Google Scholar
  11. 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.
  12. Reinhard Diestel. Graph Theory, volume 173 of Graduate texts in mathematics. Springer, 4th edition, 2012. Google Scholar
  13. Guoli Ding, Bogdan Oporowski, James G. Oxley, and Dirk Vertigan. Unavoidable minors of large 3-connected binary matroids. J. Comb. Theory, Ser. B, 66(2):334-360, 1996. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  15. Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio mathematica, 2:463-470, 1935. Google Scholar
  16. Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP. Artif. Intell., 257:61-71, 2018. Google Scholar
  17. Robert Ganian and Sebastian Ordyniak. The power of cut-based parameters for computing edge-disjoint paths. Algorithmica, 2021. To appear. Google Scholar
  18. Guilherme de C. M. Gomes, Carlos V. G. C. Lima, and Vinícius Fernandes dos Santos. Parameterized complexity of equitable coloring. Discret. Math. Theor. Comput. Sci., 21(1), 2019. Google Scholar
  19. Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey theory, volume 20. John Wiley & Sons, 1990. Google Scholar
  20. Gregory Z. Gutin, Mark Jones, and Magnus Wahlström. The mixed chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discret. Math., 30(4):2177-2205, 2016. Google Scholar
  21. Thekla Hamm. Finding linear arrangements of hypergraphs with bounded cutwidth in linear time. In Bart M. P. Jansen and Jan Arne Telle, editors, Proceedings of the 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, volume 148 of LIPIcs, pages 20:1-20:14. Schloss Dagstuhl, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.20.
  22. Svein Høgemo, Jan Arne Telle, and Erlend Raa Vågset. Linear mim-width of trees. In Ignasi Sau and Dimitrios M. Thilikos, editors, Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019, volume 11789 of LNCS, pages 218-231. Springer, 2019. Google Scholar
  23. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Mim-width III. Graph powers and generalized distance domination problems. Theor. Comput. Sci., 796:216-236, 2019. URL: https://doi.org/10.1016/j.tcs.2019.09.012.
  24. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width I. Induced path problems. Discret. Appl. Math., 278:153-168, 2020. Google Scholar
  25. Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle. Maximum matching width: New characterizations and a fast algorithm for dominating set. Discret. Appl. Math., 248:114-124, 2018. Google Scholar
  26. Ton Kloks. Treewidth: Computations and Approximations. Springer, Berlin, 1994. Google Scholar
  27. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  28. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B, 96(4):514-528, 2006. Google Scholar
  29. Michaël Rao. Clique-width of graphs defined by one-vertex extensions. Discret. Math., 308(24):6157-6165, 2008. Google Scholar
  30. Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986. Google Scholar
  31. Sigve Hortemo Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. Theor. Comput. Sci., 615:120-125, 2016. Google Scholar
  32. Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth II: algorithms for partial w-trees of bounded degree. J. Algorithms, 56(1):25-49, 2005. URL: https://doi.org/10.1016/j.jalgor.2004.12.003.
  33. Martin Vatshelle. New width parameters of graphs. PhD thesis, University of Bergen, 2012. Google Scholar
  34. Koichi Yamazaki. Inapproximability of rank, clique, boolean, and maximum induced matching-widths under small set expansion hypothesis. Algorithms, 11(11):173, 2018. 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