# Recent Advances in Positive-Instance Driven Graph Searching +
###### 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 [PERSON] (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). The parameter _treadepth_ has a similar story. It was popularized through the graph sparsity project and is theoretically well understood--but the first practical algorithm was discovered only recently by [PERSON] (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms. treewidth; pathwidth; treedepth; graph searching; positive-instance driven; color coding +
Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/)]([https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/))). Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons. small width can be used to efficiently solve the mixed Chinese postman problem [26] or to design algorithms for mixed integer linear programs [28]. Pathwidth was recently used as structural parameter to prove that the well-known vertex cover problem can be solved in polynomial time with high probability on hyperbolic random graphs (which are frequently used to model real-world networks) [29]. No matter which of these width measures we wish to utilize for a task at hand, we have to be able to compute it quickly. More crucially, most algorithms also need a witness in the form of a _decomposition_. A lot of _theoretical_ research has been performed in this direction [30; 31] and width measures such as treewidth can even be computed in linear fpt-time by [PERSON]'s famous algorithm [32]. Unfortunately, it is known that this algorithm does _not_ work in practice due to huge constants [33] (the same holds for similar algorithms for the other width measures). When it comes to implementations, small progress has been made with classical exact exponential time algorithms, which are only able to solve graphs with about 50-100 vertices. See, for instance, the QuickBB algorithm for treewidth [34], the algorithm by [PERSON], [PERSON], and [PERSON] for pathwidth [35], or a recent branch-and-bound algorithm for treedepth [36]. More progress was made with heuristics, see, for instance, [37; 38; 39] for treewidth, the algorithm by [PERSON] et al. for pathwidth [40], and Section 24 in [41] for treedepth. We may argue that, indeed, a heuristic is sufficient, as the attached solver will work correctly independently of the width of the provided decomposition--and the heuristic may produce a decomposition of \"small enough\" width. However, even a small error, something as \"off by 5\", may put the parameter to a computationally intractable range, as the dependency on the width is usually at least exponential. For instance, it was observed that small changes (even by just one or two) in the width of a tree decomposition can have a huge impact on the inference time in probabilistic networks [42].