# Recent Advances in Positive-Instance Driven Graph Searching +
## 7 Conclusions and Outlook  
Treewidth is one of the most useful graph parameters that is successfully used in many different areas. The positive-instance driven dynamic programming paradigm has led to the first practically relevant algorithm for this parameter, as well as for its close relative treedepth. We formalized such algorithms in the general setting of graph searching, which has allowed us to provide a clean and simple formulation and to extend the algorithm to many natural graph parameters.  
With a few modifications of the colosseum, our approach can also be used for the notion of _special treewidth_[88]. We assume that a similar modification may also be possible for other parameters such as _spaghetti treewidth_[89].  
We also extended the block sieve data structure to a randomized multi-level sieve that is constructed lazily and that utilizes the well-known color coding technique. By modifying the number of colorings used, we can change the probability that a non-compatible block is pruned by the sieve. Hence, introducing more and more colors makes it unlikely that non-compatible blocks are output by the sieve. On the theoretical side, we may derandomize the data structure and obtain a guarantee that certain non-compatible blocks are filtered.  
Experiments have revealed that the color coding sieve in general increases the performance of our treedepth solver \(\mathsf{PID}^{\star}\). For the instances that are currently tractable by the solver, a single random coloring provides the best overall performance, but we expect that on harder instances the theoretical guarantees of using more colorings will result in a positive practical impact. An interesting next step would be to implement the color coding sieve in state-of-the-art treewidth solvers such as [20; 53; 63], which currently perform slightly better than the state-of-the-art treedepth solvers [44; 45].  
The authors have contributed equally. All authors have read and agreed to the published version of the manuscript.  
This research received no external funding.  
**Institutional Review Board Statement:** Not applicable.  
**Informed Consent Statement:** Not applicable.  
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline  & & & & \multicolumn{4}{c}{**\(\boldsymbol{\alpha}\) of...**} & & & \\
**Graph** & \(n\) & \(m\) & **td** & **Level-1** & **Level-2** & \(\boldsymbol{\gamma=3}\) & \(\boldsymbol{\gamma=6}\) & **Level-3** & **imp. Level-3** \\ \hline exact\_057 & 50 & 75 & 13 & 0.19 & 0.31 & 0.65 & 0.87 & 0.77 & 0.97 \\ exact\_077 & 66 & 120 & 12 & 0.10 & 0.27 & 0.53 & 0.75 & 0.51 & 0.83 \\ exact\_078 & 67 & 152 & 12 & 0.04 & 0.12 & 0.26 & 0.33 & 0.13 & 0.20 \\ exact\_079 & 68 & 83 & 9 & 0.06 & 0.27 & 0.59 & 0.71 & 0.36 & 0.69 \\ exact\_083 & 70 & 274 & 22 & 0.16 & 0.33 & 0.63 & 0.79 & 0.67 & 0.92 \\ \hline \hline \end{tabular}
\end{table}
Table 6: Same as Table 4, but on instances from the PACE 2020 benchmark set [45].  
Data Availability Statement: The DIMACS graph coloring instances and the PACE 2020 instances are publicly available [45; 84]. The hyperbolic random graphs can be generated with the publicly available hyperbolic graph generator [87] and the parameters stated within the main text. The tools Jdrasil and PID\({}^{*}\) are also publicly available [20; 49].