2026-07-19T22:37:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13331 2024-03-06T10:51:43Z ddc:004 open_access

PACE Solver Description: PID^⋆ Bannach, Max Berndt, Sebastian Schuster, Martin Wienöbst, Marcel treedepth positive-instance driven 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Bannach and Sebastian Berndt and Martin Schuster and Marcel Wienöbst 2020 Is Part Of LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2020.28 urn:nbn:de:0030-drops-133312 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.28 eng https://creativecommons.org/licenses/by/3.0/legalcode