Document Open Access Logo

Optimizing Tree Decompositions in MSO

Authors Mikolaj Bojanczyk, Michal Pilipczuk

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.15.pdf
  • Filesize: 0.92 MB
  • 13 pages

Document Identifiers

Author Details

Mikolaj Bojanczyk
Michal Pilipczuk

Cite As Get BibTex

Mikolaj Bojanczyk and Michal Pilipczuk. Optimizing Tree Decompositions in MSO. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.15

Abstract

The classic algorithm of Bodlaender and Kloks solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the graph. In this work, we prove that this problem can also be solved in MSO in the following sense: for every positive integer k, there is an MSO transduction from tree decompositions of width k to tree decompositions of optimum width. Together with our recent results, this implies that for every k there exists an MSO transduction which inputs a graph of treewidth k, and nondeterministically outputs its tree decomposition of optimum width.

Subject Classification

Keywords
  • tree decomposition
  • treewidth
  • transduction
  • monadic second-order logic

Metrics

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

References

  1. Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. In CSL 2006, volume 4207 of Lecture Notes in Computer Science, pages 167-181. Springer, 2006. Google Scholar
  2. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. Google Scholar
  3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. Google Scholar
  4. 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
  5. Hans L. Bodlaender and Dimitrios M. Thilikos. Constructive linear time algorithms for branchwidth. In ICALP 1997, volume 1256 of Lecture Notes in Computer Science, pages 627-637. Springer, 1997. Google Scholar
  6. Mikołaj Bojańczyk and Michał Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In LICS 2016, pages 407-416. ACM, 2016. Google Scholar
  7. 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. Google Scholar
  8. Bruno Courcelle and Jens Lagergren. Equivalent definitions of recognizability for sets of graphs of bounded tree-width. Mathematical Structures in Computer Science, 6(2):141-165, 1996. Google Scholar
  9. Jörg Flum, Markus Frick, and Martin Grohe. Query evaluation via tree-decompositions. J. ACM, 49(6):716-752, 2002. Google Scholar
  10. Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: obstructions and algorithmic aspects. CoRR, abs/1606.05975, 2016. To appear in Proc. of IPEC 2016. Google Scholar
  11. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs, volume 57 of Annals of Discrete Mathematics. North-Holland Publishing Co., 2004. Google Scholar
  12. Jisu Jeong, Eun Jung Kim, and Sang-il Oum. Constructive algorithm for path-width of matroids. In SODA 2016, pages 1695-1704. SIAM, 2016. Google Scholar
  13. Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Trans. Comput. Log., 14(4):25, 2013. Google Scholar
  14. Nancy G. Kinnersley. The vertex separation number of a graph equals its path-width. Inf. Process. Lett., 42(6):345-350, 1992. Google Scholar
  15. Jens Lagergren and Stefan Arnborg. Finding minimal forbidden minors using a finite congruence. In ICALP 1991, volume 510 of Lecture Notes in Computer Science, pages 532-543. Springer, 1991. Google Scholar
  16. Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. J. Algorithms, 56(1):1-24, 2005. Google Scholar
  17. 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. 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