PACE Solver Description: PID*

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

doi:10.4230/LIPIcs.IPEC.2020.28

PACE Solver Description: PID*

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

Institute of Theoretical Computer Science

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.

Original language	English
Title of host publication	15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Editors	Yixin Cao, Marcin Pilipczuk
Number of pages	4
Volume	180
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date	04.12.2020
Pages	28:1--28:4
ISBN (Print)	978-3-95977-172-6
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2020.28
Publication status	Published - 04.12.2020
Event	15th International Symposium on Parameterized and Exact Computation - Online Event, Hong Kong, Hong Kong Duration: 14.12.2020 → 18.12.2020

DFG Research Classification Scheme

4.43-01 Theoretical Computer Science

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.4230/LIPIcs.IPEC.2020.28

Cite this

Bannach, M., Berndt, S., Schuster, M., & Wienöbst, M. (2020). PACE Solver Description: PID*. In Y. Cao, & M. Pilipczuk (Eds.), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) (Vol. 180, pp. 28:1--28:4). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 180). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2020.28

@inproceedings{d2fd0c31f6f64760a61590437dca87c0,

title = "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.",

author = "Max Bannach and Sebastian Berndt and Martin Schuster and Marcel Wien{\"o}bst",

year = "2020",

month = dec,

day = "4",

doi = "10.4230/LIPIcs.IPEC.2020.28",

language = "English",

isbn = "978-3-95977-172-6",

volume = "180",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "28:1----28:4",

editor = "Cao, {Yixin } and Pilipczuk, {Marcin }",

booktitle = "15th International Symposium on Parameterized and Exact Computation (IPEC 2020)",

note = "15th International Symposium on Parameterized and Exact Computation , IPEC 2020 ; Conference date: 14-12-2020 Through 18-12-2020",

}

Bannach, M, Berndt, S, Schuster, M & Wienöbst, M 2020, PACE Solver Description: PID*. in Y Cao & M Pilipczuk (eds), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). vol. 180, Leibniz International Proceedings in Informatics (LIPIcs), vol. 180, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 28:1--28:4, 15th International Symposium on Parameterized and Exact Computation , Hong Kong, Hong Kong, 14.12.20. https://doi.org/10.4230/LIPIcs.IPEC.2020.28

PACE Solver Description: PID*. / Bannach, Max; Berndt, Sebastian; Schuster, Martin et al.
15th International Symposium on Parameterized and Exact Computation (IPEC 2020). ed. / Yixin Cao; Marcin Pilipczuk. Vol. 180 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. p. 28:1--28:4 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 180).

Research output: Chapters in Books/Reports/Conference Proceedings › Conference contribution › peer-review

TY - GEN

T1 - PACE Solver Description: PID*

AU - Bannach, Max

AU - Berndt, Sebastian

AU - Schuster, Martin

AU - Wienöbst, Marcel

PY - 2020/12/4

Y1 - 2020/12/4

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.IPEC.2020.28

DO - 10.4230/LIPIcs.IPEC.2020.28

M3 - Conference contribution

SN - 978-3-95977-172-6

VL - 180

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 28:1--28:4

BT - 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

A2 - Cao, Yixin

A2 - Pilipczuk, Marcin

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 15th International Symposium on Parameterized and Exact Computation

Y2 - 14 December 2020 through 18 December 2020

ER -