# Recent Advances in Positive-Instance Driven Graph Searching +
###### Abstract
A similar effect was observed in recent advances of implementing a lightweight model checker for a fragment of MSO [7], where it turned out to be beneficial to invest additional time in order to obtain an optimal tree decomposition rather than relying on faster heuristics. It is therefore a natural and important task to build practical fast algorithms to determine parameters such as the treewidth, pathwidth, or treedepth of a graph exactly. To tackle this issue, the fpt-community came up with a contest, the Parameterized Algorithms and Computational Experiments (PACE) challenge [43; 44; 45], with the goal of finding new exact algorithms to determine the exact treewidth or treedepth of a graph. Besides many, one important result of the challenge was a new combinatorial algorithm due to [PERSON], which computes the treewidth of an input graph exactly and astonishingly fast on a wide range of instances. An implementation of this algorithm by [PERSON] himself [46] won the corresponding track in the PACE challenge in 2016 [43] and an alternative implementation due to [PERSON] and [PERSON] [47] won in 2017 [44]. In 2020, many participants adapted the original algorithm to treedepth [45; 48; 49]. [PERSON]'s original algorithm is based on a dynamic program by [PERSON], [PERSON], and [PERSON] [50] for computing tree decompositions. This algorithm has a game theoretic characterization that can be used to generalize the algorithm to other width measures such as treedepth. [PERSON] has improved his algorithm for the second iteration of the PACE by applying his framework to the algorithm by [PERSON] and [PERSON] [51; 52], see, for instance, [53] for a recent evaluation of this version of the algorithm. While [PERSON] and [PERSON]'s algorithm has a game theoretic characterization as well [54], it is still unclear how it can be generalized to other width measures. We focus on [PERSON]'s first algorithm and characterize it in a unifying way that allows us to compute not just the treewidth of a graph but, with the same algorithm, the pathwidth, treedepth, \(q\)-branched treewidth, and dependency treewidth as well. Perhaps even more importantly, our description of the algorithm in a game theoretic framework is simple and intuitive and can be implemented quite directly. In fact, our treewidth and treedepth solvers Jdrasil and PID\({}^{\star}\) are based on this characterization [20; 49]. The detailed contributions of this paper are the following:  
**Contribution I: A Simple Description of [PERSON]'s First Algorithm. **  
We describe [PERSON]'s algorithm as a well-known graph searching game. This provides a link to known theory and allows us to analyze the algorithm in depth. **Contribution II. Extending [PERSON]'s Algorithm to Other Parameters**  
The game theoretic point of view allows us to extend the algorithm naturally to various other parameters--including pathwidth and treedepth. **Contribution III: A Novel Randomized Data Structure. **  
The bottleneck in positive-instance driven algorithms is the enumeration of already computed solutions. We present a lazily constructed randomized data structure that, in contrast to existing data structures for this task, provides a guarantee that certain useless solutions are not enumerated with high probability.