Document Open Access Logo

Positive-Instance Driven Dynamic Programming for Treewidth

Author Hisao Tamaki

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.68.pdf
  • Filesize: 489 kB
  • 13 pages

Document Identifiers

Author Details

Hisao Tamaki

Cite As Get BibTex

Hisao Tamaki. Positive-Instance Driven Dynamic Programming for Treewidth. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 68:1-68:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.68

Abstract

Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is positive-instance driven (PID), if it generates positive subproblem instances, but not negative ones, building each on smaller positive instances.

We take the dynamic programming scheme due to Bouchitté and Todinca for treewidth computation, which is based on minimal separators and potential maximal cliques, and design a variant (for the decision version of the problem) with a natural PID implementation. The resulting algorithm performs extremely well: it solves a number of standard benchmark instances for which the optimal solutions have not previously been known. Incorporating a new heuristic algorithm for detecting safe separators, it also solves all of the 100 public instances posed by the exact treewidth track in PACE 2017, a competition on algorithm implementation.

We describe the algorithm and prove its correctness. We also perform an experimental analysis counting combinatorial structures involved, which gives insights into the advantage of our approach over more conventional approaches and points to the future direction of theoretical and engineering research on treewidth computation.

Subject Classification

Keywords
  • treewidth
  • dynamic programming
  • minimal separators
  • potential maximal cliques
  • positive instances

Metrics

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

References

  1. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277-284, 1987. Google Scholar
  2. Jeremias Berg and Matti Järvisalo. Sat-based approaches to treewidth computation: an evaluation. In Tools with Artificial Intelligence (ICTAI), 2014 IEEE 26th International Conference on, pages 328-335. IEEE, 2014. Google Scholar
  3. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, 25(6):1305-1317, 1996. Google Scholar
  4. Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems, 50(3):420-432, 2012. Google Scholar
  5. Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. On exact algorithms for treewidth. ACM Transactions on Algorithms (TALG), 9(1):12, 2012. Google Scholar
  6. Hans L. Bodlaender and Arie M. C. A. Koster. Safe separators for treewidth. Discrete Mathematics, 306(3):337-350, 2006. Google Scholar
  7. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, 51(3):255-269, 2007. Google Scholar
  8. Hans L. Bodlaender, Thomas Wolle, and Arie M. C. A. Koster. Contraction and treewidth lower bounds. J. Graph Algorithms Appl., 10(1):5-49, 2006. Google Scholar
  9. Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing, 31(1):212-232, 2001. Google Scholar
  10. 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 LIPIcs - Leibniz International Proceedings in Informatics, volume 63. Schloss Dagstuhl-Leibniz - Zentrum fürr Informatik, 2017. Google Scholar
  11. Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, and Yngve Villanger. Exact algorithms for treewidth and minimum fill-in. SIAM Journal on Computing, 38(3):1058-1079, 2008. Google Scholar
  12. Fedor V. Fomin and Yngve Villanger. Treewidth computation and extremal combinatorics. Combinatorica, pages 1-20, 2012. Google Scholar
  13. GitHub repository for TCS-Meiji on PACE2017 Track A submission. https://github.com/TCS-Meiji/PACE2017-TrackA. Public since: 2017-05-01.
  14. Vibhav Gogate and Rina Dechter. A complete anytime algorithm for treewidth. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 201-208. AUAI Press, 2004. Google Scholar
  15. David S. Johnson and Michael A. Trick. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993, volume 26. American Mathematical Soc., 1996. Google Scholar
  16. Nysret Musliu. An iterative heuristic algorithm for tree decomposition. In Recent Advances in Evolutionary Computation for Combinatorial Optimization, pages 133-150. Springer, 2008. Google Scholar
  17. Neil Robertson and Paul D. Seymour. Graph minors. II. algorithmic aspects of tree-width. Journal of algorithms, 7(3):309-322, 1986. Google Scholar
  18. Neil Robertson and Paul D. Seymour. Graph minors. XX. wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. Google Scholar
  19. Marko Samer and Helmut Veith. Encoding treewidth into SAT. In International Conference on Theory and Applications of Satisfiability Testing, pages 45-50. Springer, 2009. Google Scholar
  20. Iztok Savnik. Index data structure for fast subset and superset queries. In International Conference on Availability, Reliability, and Security, pages 134-148. Springer, 2013. Google Scholar
  21. The Parameterized Algorithms and Computational Experiments Challenge. https://pacechallenge.wordpress.com. Accessed: 2017-06-30.
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