Positive-Instance Driven Dynamic Programming for Graph Searching

Max Bannach*, Sebastian Berndt

*Corresponding author for this work


Research on the similarity of a graph to being a tree – called the treewidth of the graph – has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). We give an alternative and intuitive view on this algorithm from the perspective of the corresponding configuration graphs in certain two-player games. This allows us to develop PID-algorithms for a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We analyse the worst case behaviour of the approach on some well-known graph classes and perform an experimental evaluation on real world and random graphs.

Original languageEnglish
Title of host publicationWADS 2019: Algorithms and Data Structures
EditorsZachary Friggstad, Jörg-Rüdiger Sack, Mohammad R Salavatipour
Number of pages14
Volume11646 LNCS
PublisherSpringer, Cham
Publication date12.07.2019
ISBN (Print)978-3-030-24765-2
ISBN (Electronic)978-3-030-24766-9
Publication statusPublished - 12.07.2019
Event16th International Symposium on Algorithms and Data Structures - Edmonton, Canada
Duration: 05.08.201907.08.2019
Conference number: 229299


Dive into the research topics of 'Positive-Instance Driven Dynamic Programming for Graph Searching'. Together they form a unique fingerprint.

Cite this