PACE Solver Description: Bute-Plus: A Bottom-Up Exact Solver for Treedepth

Author James Trimble



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.34.pdf
  • Filesize: 309 kB
  • 4 pages

Document Identifiers

Author Details

James Trimble
  • School of Computing Science, University of Glasgow, Scotland, UK

Acknowledgements

I would like to thank the PACE 2020 program committee and the optil.io team for a well-organised and enjoyable contest.

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
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