Positive-Instance Driven Dynamic Programming for Graph Searching (WADS 2019)

Abstract

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 program- ming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Al- gorithms producing only such subinstances are called positive-instance driven (PID). We give an alternative and intuitive view on this algo- rithm 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, path- width, q-branched treewidth, treedepth and dependency-treewidth. 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.

Publication
In WADS Algorithms and Data Structures Symposium