LIPIcs.IPEC.2020.34.pdf
- Filesize: 309 kB
- 4 pages
Document
PACE Solver Description: Bute-Plus: A Bottom-Up Exact Solver for Treedepth
Author
James Trimble 
-
Part of:
Volume:
15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Author Details
Acknowledgements
I would like to thank the PACE 2020 program committee and the optil.io team for a well-organised and enjoyable contest.
Cite As Get BibTex
James Trimble. PACE Solver Description: Bute-Plus: A Bottom-Up Exact Solver for Treedepth. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 34:1-34:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.34
Abstract
This note introduces Bute-Plus, an exact solver for the treedepth problem. The core of the solver is a positive-instance driven dynamic program that constructs an elimination tree of minimum depth in a bottom-up fashion. Three features greatly improve the algorithm’s run time. The first of these is a specialised trie data structure. The second is a domination rule. The third is a heuristic presolve step can quickly find a treedepth decomposition of optimal depth for many instances.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
- Theory of computation → Algorithm design techniques
Keywords
- Treedepth
- Elimination Tree
- Graph Algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Max Bannach and Sebastian Berndt. Positive-instance driven dynamic programming for graph searching. In Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pages 43-56. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_4.
- Robert Ganian, Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. SAT-encodings for treecut width and treedepth. In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019., pages 117-129. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975499.10.
- George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Scientific Computing, 20(1):359-392, 1998. URL: https://doi.org/10.1137/S1064827595287997.
- Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
- Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
- Iztok Savnik. Index data structure for fast subset and superset queries. In Availability, Reliability, and Security in Information Systems and HCI - IFIP WG 8.4, 8.9, TC 5 International Cross-Domain Conference, CD-ARES 2013, Regensburg, Germany, September 2-6, 2013. Proceedings, volume 8127 of Lecture Notes in Computer Science, pages 134-148. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40511-2_10.
- Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. J. Comb. Optim., 37(4):1283-1311, 2019. URL: https://doi.org/10.1007/s10878-018-0353-z.
- Ben Tilly. Fast data structure for finding strict subsets (from a given list). Stack Overflow. Version: 2011-06-29. URL: https://stackoverflow.com/a/6514445/3347737.
- James Trimble. An algorithm for the exact treedepth problem. In 18th International Symposium on Experimental Algorithms, SEA 2020, June 16-18, 2020, Catania, Italy, volume 160 of LIPIcs, pages 19:1-19:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.19.