Document Open Access Logo

An Algorithm for the Exact Treedepth Problem

Author James Trimble

PDF
Thumbnail PDF

File

LIPIcs.SEA.2020.19.pdf
  • Filesize: 493 kB
  • 14 pages

Document Identifiers

Author Details

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

Funding

  • Trimble, James: This work was supported by the Engineering and Physical Sciences Research Council (grant number EP/R513222/1).

Acknowledgements

Thanks to Ciaran McCreesh, David Manlove, Patrick Prosser and the anonymous referees for their helpful feedback, and to Robert Ganian, Neha Lodha, and Vaidyanathan Peruvemba Ramaswamy for providing software for the SAT encoding.

Cite AsGet BibTex

James Trimble. An Algorithm for the Exact Treedepth Problem. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SEA.2020.19

Abstract

We present a novel algorithm for the minimum-depth elimination tree problem, which is equivalent to the optimal treedepth decomposition problem. Our algorithm makes use of two cheaply-computed lower bound functions to prune the search tree, along with symmetry-breaking and domination rules. We present an empirical study showing that the algorithm outperforms the current state-of-the-art solver (which is based on a SAT encoding) by orders of magnitude on a range of graph classes.

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
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Bengt Aspvall and Pinar Heggernes. Finding minimum height elimination trees for interval graphs in polynomial time. BIT Numerical Mathematics, 34(4):484-509, December 1994. URL: https://doi.org/10.1007/BF01934264.
  2. Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza. Rankings of graphs. SIAM J. Discrete Math., 11(1):168-181, 1998. URL: https://doi.org/10.1137/S0895480195282550.
  3. Jitender S. Deogun, Ton Kloks, Dieter Kratsch, and Haiko Müller. On vertex ranking for permutations and other graphs. In Patrice Enjalbert, Ernst W. Mayr, and Klaus W. Wagner, editors, STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings, volume 775 of Lecture Notes in Computer Science, pages 747-758. Springer, 1994. URL: https://doi.org/10.1007/3-540-57785-8_187.
  4. Jitender S. Deogun, Ton Kloks, Dieter Kratsch, and Haiko Müller. On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discrete Applied Mathematics, 98(1-2):39-63, 1999. URL: https://doi.org/10.1016/S0166-218X(99)00179-1.
  5. Niklas Eén and Niklas Sörensson. An extensible SAT-solver. In Enrico Giunchiglia and Armando Tacchella, editors, Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5-8, 2003 Selected Revised Papers, volume 2919 of Lecture Notes in Computer Science, pages 502-518. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-24605-3_37.
  6. Robert Ganian, Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. SAT-encodings for treecut width and treedepth. In Stephen G. Kobourov and Henning Meyerhenke, editors, 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.
  7. Robert Ganian, Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. SAT-encodings for treecut width and treedepth. CoRR, abs/1911.12995, 2019. URL: http://arxiv.org/abs/1911.12995.
  8. Chris Groër, Blair D Sullivan, and Dinesh Weerapurage. Inddgo: Integrated network decomposition & dynamic programming for graph optimization. ORNL/TM-2012, 176, 2012. Google Scholar
  9. Gregory Z. Gutin, Mark Jones, and Magnus Wahlström. The mixed Chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discrete Math., 30(4):2177-2205, 2016. URL: https://doi.org/10.1137/15M1034337.
  10. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60(0):94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
  11. Asier Mujika. About tree-depth. Bachelor’s thesis, Universidad del País Vasco, 2015. Google Scholar
  12. 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.
  13. A. Pothen. The complexity of optimal elimination trees. Technical Report CS 88-16, Department of Computer Science, Penn State, 1988. Google Scholar
  14. Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 931-942. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_77.
  15. Colva M. Roney-Dougal, Ian P. Gent, Tom Kelsey, and Steve Linton. Tractable symmetry breaking using restricted search trees. In Ramón López de Mántaras and Lorenza Saitta, editors, Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI'2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, August 22-27, 2004, pages 211-215. IOS Press, 2004. Google Scholar
  16. Alejandro A. Schäffer. Optimal node ranking of trees in linear time. Inf. Process. Lett., 33(2):91-96, 1989. URL: https://doi.org/10.1016/0020-0190(89)90161-0.
  17. Earl Zmijewski and John R Gilbert. A parallel algorithm for large sparse Cholesky factorization on a multiprocessor. Technical Report TR 86-733, Cornell University, Ithaca, NY, 1986. 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