License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.28
URN: urn:nbn:de:0030-drops-133312
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13331/
Bannach, Max ;
Berndt, Sebastian ;
Schuster, Martin ;
Wienöbst, Marcel
PACE Solver Description: PID^⋆
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.
BibTeX - Entry
@InProceedings{bannach_et_al:LIPIcs:2020:13331,
author = {Max Bannach and Sebastian Berndt and Martin Schuster and Marcel Wien{\"o}bst},
title = {{PACE Solver Description: PID^⋆}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {28:1--28:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-172-6},
ISSN = {1868-8969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13331},
URN = {urn:nbn:de:0030-drops-133312},
doi = {10.4230/LIPIcs.IPEC.2020.28},
annote = {Keywords: treedepth, positive-instance driven}
}
