Positive-instance driven dynamic programming for treewidth. (English) Zbl 1442.90198
Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 68, 13 p. (2017).
Summary: 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 V. Bouchitté and I. Todinca [SIAM J. Comput. 31, No. 1, 212–232 (2001; Zbl 0987.05085)] 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.
For the entire collection see [Zbl 1372.68019].
We take the dynamic programming scheme due to V. Bouchitté and I. Todinca [SIAM J. Comput. 31, No. 1, 212–232 (2001; Zbl 0987.05085)] 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.
For the entire collection see [Zbl 1372.68019].
MSC:
| 90C39 | Dynamic programming |
| 05C05 | Trees |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 91B06 | Decision theory |
Keywords:
treewidth; dynamic programming; minimal separators; potential maximal cliques; positive instancesCitations:
Zbl 0987.05085Software:
DIMACSReferences:
| [1] | Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding em beddings in a {\it k}-tree. {\it SIAM Journal on Algebraic Discrete Methods}, 8(2):277-284, 1987. · Zbl 0611.05022 |
| [2] | Jeremias Berg and Matti Järvisalo. Sat-based approaches to treewidth computation: an evaluation. In {\it Tools with Artificial Intelligence (ICTAI), 2014 IEEE 26th International} {\it Conference on}, pages 328-335. IEEE, 2014. |
| [3] | Hans L. Bodlaender.A linear-time algorithm for finding tree-decompositions of small treewidth. {\it SIAM Journal on computing}, 25(6):1305-1317, 1996. · Zbl 0864.68074 |
| [4] | Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Di mitrios M. Thilikos. A note on exact algorithms for vertex ordering problems on graphs. {\it Theory of Computing Systems}, 50(3):420-432, 2012. · Zbl 1253.68164 |
| [5] | Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Di mitrios M. Thilikos. On exact algorithms for treewidth. {\it ACM Transactions on Algorithms} {\it (TALG)}, 9(1):12, 2012. · Zbl 1301.05328 |
| [6] | Hans L. Bodlaender and Arie M. C. A. Koster. Safe separators for treewidth. {\it Discrete} {\it Mathematics}, 306(3):337-350, 2006. · Zbl 1084.05065 |
| [7] | Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. {\it The Computer Journal}, 51(3):255-269, 2007. |
| [8] | Hans L. Bodlaender, Thomas Wolle, and Arie M. C. A. Koster. Contraction and treewidth lower bounds. {\it J. Graph Algorithms Appl.}, 10(1):5-49, 2006. · Zbl 1161.68644 |
| [9] | Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. {\it SIAM Journal on Computing}, 31(1):212-232, 2001. · Zbl 0987.05085 |
| [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 {\it LIPIcs - Leibniz International Proceedings in Informatics}, volume 63. Schloss Dagstuhl-Leibniz - Zentrum fürr Informatik, 2017. |
| [11] | Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, and Yngve Villanger. Exact algorithms for treewidth and minimum fill-in. {\it SIAM Journal on Computing}, 38(3):1058-1079, 2008. · Zbl 1163.05320 |
| [12] | Fedor V. Fomin and Yngve Villanger. Treewidth computation and extremal combinatorics. {\it Combinatorica}, pages 1-20, 2012. · Zbl 1289.05447 |
| [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 {\it Proceed-} {\it ings of the 20th conference on Uncertainty in artificial intelligence}, pages 201-208. AUAI Press, 2004. · Zbl 1152.68560 |
| [15] | David S. Johnson and Michael A. Trick.{\it Cliques, coloring, and satisfiability: second} {\it DIMACS implementation challenge, October 11-13, 1993}, volume 26. American Math ematical Soc., 1996. · Zbl 0875.68678 |
| [16] | Nysret Musliu. An iterative heuristic algorithm for tree decomposition. In {\it Recent Advances} {\it in Evolutionary Computation for Combinatorial Optimization}, pages 133-150. Springer, 2008. · Zbl 1159.90499 |
| [17] | Neil Robertson and Paul D. Seymour. Graph minors. II. algorithmic aspects of tree-width. {\it Journal of algorithms}, 7(3):309-322, 1986. · Zbl 0611.05017 |
| [18] | Neil Robertson and Paul D. Seymour. Graph minors. XX. wagner’s conjecture. {\it Journal of} {\it Combinatorial Theory, Series B}, 92(2):325-357, 2004. · Zbl 1061.05088 |
| [19] | Marko Samer and Helmut Veith. Encoding treewidth into SAT. In {\it International Conference} {\it on Theory and Applications of Satisfiability Testing}, pages 45-50. Springer, 2009. · Zbl 1247.68259 |
| [20] | Iztok Savnik. Index data structure for fast subset and superset queries. In {\it International} {\it Conference on Availability, Reliability, and Security}, pages 134-148. Springer, 2013. |
| [21] | The Parameterized Algorithms and Computational Experiments Challenge.https:// pacechallenge.wordpress.com. Accessed: 2017-06-30. · Zbl 1391.93258 |
| [22] | :13 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
