LIPIcs.IPEC.2020.28.pdf
- Filesize: 372 kB
- 4 pages
Document
PACE Solver Description: PID^⋆
Authors
Max Bannach 
,
Sebastian Berndt ,
-
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
Cite As Get BibTex
Max Bannach, Sebastian Berndt, Martin Schuster, and Marcel Wienöbst. PACE Solver Description: PID^⋆. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.28
Abstract
This document provides a short overview of our treedepth solver PID^{⋆} in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games - which include the game theoretic characterization of treedepth. Our solver PID^{⋆} is build on top of this characterization.
Subject Classification
ACM Subject Classification
- Theory of computation → Parameterized complexity and exact algorithms
Keywords
- treedepth
- positive-instance driven
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 Proceedings of the 16th International Symposium on Algorithms and Data Structures, 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 21th Workshop on Algorithm Engineering and Experiments, 2019. URL: https://doi.org/10.1137/1.9781611975499.10.
- Archontia C. Giannopoulou, Paul Hunter, and Dimitrios M. Thilikos. Lifo-search: A min-max theorem and a searching game for cycle-rank and tree-depth. Discret. Appl. Math., 160(15):2089-2097, 2012. URL: https://doi.org/10.1016/j.dam.2012.03.015.
- Yasuaki Kobayashi and Hisao Tamaki. Treedepth Parameterized by Vertex Cover Number. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016. URL: https://doi.org/10.4230/LIPIcs.IPEC.2016.18.
-
Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. J. Comb. Optim., 37(4):1283-1311, 2019.
