# Recent Advances in Positive-Instance Driven Graph Searching +
## 6 Experimental Evaluation of Color Coding Sieves
### Sieve-Quality of the Individual Layers  
So far, we measured the performance boost obtained by adding a color coding sieve to PID\({}^{*}\) with respect to the overall time the solver needs to solve an instance. In this section, we rather focus on the quality of the individual layers of the sieve. That is, we do _not_ measure the time used to solve an instance but measure the _amount_ of blocks that a sieve filtered. In more detail, we measure the _total number of blocks_ generated by PID\({}^{*}\) (that is, the total number of blocks inserted into the sieve) and the number of _compatible blocks_ that were filtered from the output of the sieve (over the complete run of the solver). We compare this number with the _number of loaded blocks_, which is the number of blocks returned by the sieve. Of course, all compatible blocks are loaded, but (if the sieve works poorly) many other blocks may be loaded, too. We measure the _performance of the sieve_ as the fraction of falsely loaded blocks over all non-compatible blocks. See Table 3 for the exact terminology. Observe that, in the light of Corollary 2 and Theorem 4, the performance of a color coding sieve converges to \(1\) if \(\gamma\), the number of colorings, converges to infinity. See Figure 10 for an illustrative example. Figure 9: A cumulative distribution function plot that shows the performance of PID\({}^{*}\) without color coding sieves (-wo), with just the lazily built set trie (-trie), with the full color coding sieve and \(\gamma=1\) (-color-1), and with the full color coding sieve and \(\gamma=2\) (-color-2). The experiments are performed on the set of \(210\) hyperbolic random graphs described in Table 1. \begin{table}
\begin{tabular}{r l l} \hline \hline
**Variable** & **Meaning** & **Comment** \\ \hline \(t\) & Total number of blocks. & \\ \(c\) & Number of compatible blocks. & \(c\leq t\) \\ \(\ell\) & Number of blocks loaded by the sieve. & \(c\leq\ell\leq t\) \\ \(\alpha\) & Performance as \(\alpha=1-\frac{\ell-\ell}{t-\ell}\) & \(\alpha=0\) for a trivial sieve \\  & & \(\alpha=1\) for a perfect sieve \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Variables used to describe the performance of a sieve. The values \(t\), \(c\) and \(\ell\) are considered over a complete run of the solver for a given instance, e. g., summed over various values for the target width \(k\). For the following experiments, we only use _a single layer_ of the color coding sieve and make all measurements with respect to a complete run of the solver for a given instance (i. e., summed over various values of the target width \(k\)). Since we aim to obtain a good estimation of the actual performance of the various sieves via experimental means, we consider rather difficult instances in this section. First, in Table 4, we consider \(n\times n\)-grid graphs, which are well-known to be difficult for various graph decomposition algorithms. Secondly, we hand-crafted a set of instances that are particularly difficult for the positive-instance driven approach. Let a \((n,d,c)\)-spider be the graph obtained by the following procedure: start with a star with \(n\) leaves, then replace every edge by a path with \(d\) vertices, and finally replace every vertex by a clique on \(c\) vertices that is fully-connected to the vertices of adjacent cliques. (Intuitively, a star is a worst-case instance for the positive-instance driven approach, as initially only the leaves are positive subproblems and, by trying to glue them together, the solver has to explore all \(2^{n}\) subsets of the leaves. By stretching and thickening the edges, we enforce that this behaviour stays the same and circumvent heuristics internally used by the solver.) The corresponding experiment is summarized in Table 5. Finally, we performed the experiment on a set of instances from the PACE 2020 benchmark set ([PERSON], 2020) (see Section 6). The results are presented in Table 6.  
From the experimental data shown in Tables 4-6, we conclude three observations: First, the level-1 sieve alone does not much.