Document Open Access Logo

PACE Solver Description: Computing Exact Treedepth via Minimal Separators

Authors Zijian Xu, Dejun Mao, Vorapong Suppakitpaisarn

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.31.pdf
  • Filesize: 384 kB
  • 4 pages

Document Identifiers

Author Details

Zijian Xu
  • The University of Tokyo, Japan
Dejun Mao
  • The University of Tokyo, Japan
Vorapong Suppakitpaisarn
  • The University of Tokyo, Japan

Cite As Get BibTex

Zijian Xu, Dejun Mao, and Vorapong Suppakitpaisarn. PACE Solver Description: Computing Exact Treedepth via Minimal Separators. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 31:1-31:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.IPEC.2020.31

Abstract

This is a description of team xuzijian629’s treedepth solver submitted to PACE 2020. As we use a top-down approach, we enumerate all possible minimal separators at each step. The enumeration is sped up by several novel pruning techniques and is based on our conjecture that we can always have an optimal decomposition without using separators with size larger than treewidth. Although we cannot theoretically guarantee that our algorithm based on the unproved conjecture can always give an optimal solution, it can give optimal solutions for all instances in our experiments. The algorithm solved 68 private instances and placed 5th in the competition.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Treedepth
  • Minimal Separators
  • Experimental Algorithm

Metrics

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

Supplementary Materials

References

  1. Haeder Y Althoby, Mohamed Didi Biha, and André Sesboüé. Exact and heuristic methods for the vertex separator problem. Computers & Industrial Engineering, 139:106135, 2020. Google Scholar
  2. Hans L Bodlaender and Arie MCA Koster. Treewidth computations ii. lower bounds. Information and Computation, 209(7):1103-1119, 2011. Google Scholar
  3. Hans L Bodlaender, Arie MCA Koster, and Thomas Wolle. Contraction and treewidth lower bounds. In European Symposium on Algorithms, pages 628-639. Springer, 2004. Google Scholar
  4. Dariusz Dereniowski and Adam Nadolski. Vertex rankings of chordal graphs and weighted trees. Information Processing Letters, 98(3):96-100, 2006. Google Scholar
  5. Vibhav Gogate and Rina Dechter. A complete anytime algorithm for treewidth. arXiv preprint, 2012. URL: http://arxiv.org/abs/1207.4109.
  6. David W Matula and Leland L Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM), 30(3):417-427, 1983. Google Scholar
  7. James Trimble. An algorithm for the exact treedepth problem. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.08959.
  8. Zijian Xu and Vorapong Suppakitpaisarn. On the size of minimal separators for treedepth decomposition, 2020. URL: http://arxiv.org/abs/2008.09822.
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