Document Open Access Logo

On Tamaki’s Algorithm to Compute Treewidths

Authors Ernst Althaus , Daniela Schnurbusch, Julian Wüschner, Sarah Ziegler

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.9.pdf
  • Filesize: 0.81 MB
  • 18 pages

Document Identifiers

Author Details

Ernst Althaus
  • Johannes Gutenberg-Universität Mainz, Germany
Daniela Schnurbusch
  • Johannes Gutenberg-Universität Mainz, Germany
Julian Wüschner
  • Johannes Gutenberg-Universität Mainz, Germany
Sarah Ziegler
  • Johannes Gutenberg-Universität Mainz, Germany

Cite AsGet BibTex

Ernst Althaus, Daniela Schnurbusch, Julian Wüschner, and Sarah Ziegler. On Tamaki’s Algorithm to Compute Treewidths. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SEA.2021.9

Abstract

We revisit the exact algorithm to compute the treewidth of a graph of Tamaki and present it in a way that facilitates improvements. The so-called I-blocks and O-blocks enumerated by the algorithm are interpreted as subtrees of a tree-decomposition that is constructed. This simplifies the proof of correctness and allows to discard subtrees from the enumeration by some simple observations. In our experiments, we show that one of these modifications in particular reduces the number of enumerated objects considerably.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Tree Decomposition
  • Exact Algorithm
  • Algorithms Engineering

Metrics

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

Supplementary Materials

References

  1. Ernst Althaus and Sarah Ziegler. Optimal tree decompositions revisited: A simpler linear-time FPT algorithm. CoRR, abs/1912.09144, 2019. URL: http://arxiv.org/abs/1912.09144.
  2. Ernst Althaus and Sarah Ziegler. Optimal tree decompositions revisited: A simpler linear-time fpt algorithm. In: Gentile, C., Stecca, G., Ventura, P. (eds) Graphs and Combinatorial Optimization: from Theory to Applications (CTW2020 Proceedings), 2020. AIRO Springer Series, vol 5. Springer, 2021. Google Scholar
  3. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM JOURNAL OF DISCRETE MATHEMATICS, 8(2):277-284, 1987. Google Scholar
  4. Hans Bodlaender, Arie Koster, Frank Eijkhof, and Linda C. Gaag. Pre-processing for triangulation of probabilistic networks, April 2002. Google Scholar
  5. 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.
  6. 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.
  7. Hans L. Bodlaender and Arie M. C. A. Koster. Safe separators for treewidth. Discret. Math., 306(3):337-350, 2006. URL: https://doi.org/10.1016/j.disc.2005.12.017.
  8. Hans L. Bodlaender and Arie M. C. A. Koster. Safe separators for treewidth. Discrete Math., 306(3):337–350, 2006. Google Scholar
  9. 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.
  10. Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput., 31:212-232, 2001. 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. Michael Hamann and Ben Strasser. Graph bisection with pareto optimization. ACM J. Exp. Algorithmics, 23, 2018. URL: https://doi.org/10.1145/3173045.
  13. Neil Robertson and P.D Seymour. Graph minors. ii. algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986. URL: https://doi.org/10.1016/0196-6774(86)90023-4.
  14. Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 68:1-68:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.68.
  15. Hisao Tamaki. A heuristic use of dynamic programming to upperbound treewidth. CoRR, abs/1909.07647, 2019. URL: http://arxiv.org/abs/1909.07647.
  16. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, September 2000. 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