PACE Solver Description: PID*

Max Bannach, Sebastian Berndt, Martin Schuster, Marcel Wienöbst


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.
Original languageEnglish
Title of host publication15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
EditorsYixin Cao, Marcin Pilipczuk
Number of pages4
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date04.12.2020
ISBN (Print)978-3-95977-172-6
Publication statusPublished - 04.12.2020
Event15th International Symposium on Parameterized and Exact Computation - Online Event, Hong Kong, Hong Kong
Duration: 14.12.202018.12.2020

DFG Research Classification Scheme

  • 409-01 Theoretical Computer Science


Dive into the research topics of 'PACE Solver Description: PID*'. Together they form a unique fingerprint.

Cite this