# Recent Advances in Positive-Instance Driven Graph Searching +
## 6 Experimental Evaluation of Color Coding Sieves
### Color Coding Sieves on Hyperbolic Random Graphs  
In this section, we investigate the potential performance boost obtained by using coloring coding sieves on _hyperbolic random graphs_. We use the same experimental setup as in the last section and, again, equip our treedepth solver \(\mathsf{PID}^{*}\)[49] with the color coding sieve data structure. In contrast to the last section, we will now:  
1. [noitemsep,topsep=0 pt]
2. Vary the used layers and the number of colorings \(\gamma\);
3. Run the solver on _random graphs_ rather than predefined benchmark sets. For this experiment, we use _hyperbolic random graphs_, which are known to replicate many structural properties of real-world networks [85; 86]. Loosely speaking, these graphs are generated by sampling points randomly in a disk (these are the vertices) and by connecting points by an edge if their _hyperbolic distance_ is smaller than some predefined threshold. Figure 8: Scatter plots that show the performance of \(\mathsf{PID}^{*}\) without color coding sieves compared to the performance of the solver with them enabled (\(\gamma=1\) and a randomly generated coloring is used). The left plot contains the DIMACS graph coloring instances, the right plot the PACE 2020 test set. Each point corresponds to an instance; the \(x\)-axis is the time needed by the solver using color coding sieves and the \(y\)-axis without using this feature. The color of the dot indicates which version was better; it is gray if they are equal. If a solver needed more than 10 min for an instance, the coordinate is set to the red dotted line. We generated a set of 210 hyperbolic random graphs using the _Hyperbolic Graph Generator_[87]. The generator expects six parameters that we set as shown in Table 1. The solver \(\mathsf{PID^{*}}\) was used with the four configurations explained in Table 2, whereby the level-2 sieves always use uniformly sampled random colorings. All configuration of the solver were run on all instances for at most 30 min. The results of the experiment are illustrated in a cumulative distribution function plot in Figure 9. Various interesting findings are contained in the plot: First, we can observe that the core solver without any sieve layer (-wo) cannot fully utilize the provided 30 min time window. All instances solved by this configuration are solved within 20 min and, indeed, afterwards the amount of blocks becomes too large to be enumerated naively. Second, we see the small (and expected) disadvantage of solvers with color coding sieves (-trie and -color-1) compared to the core algorithm (-wo) on \"easy\" instances (that can be solved in a minute or less). Of course, using involved data structures comes with an overhead and, if there are simply not enough blocks, we may not overcome this disadvantage with the improvements provided by the data structure. However, we can also observe that the performance of the solver with lazily built tries (-trie) and with the full color coding sieve (-color-1) quickly outperforms the core solver on the remaining instances. For the same reason as mentioned above, the lazily built set trie alone is better than the whole sieve on \"medium hard\" instance (solvable in about five minutes). Then, on even harder instances with more blocks, the additional layers can be utilized and the full color coding sieve provides the overall best performance. Third, we can observe that, on this test set, choosing \(\gamma>1\) (-color-2) has no positive effect compared to using \(\gamma=1\) (-color-1). Adding more colorings increases the overhead of the data structure and, thus, a negative effect is expected if a layer cannot be fully utilized. Here, we conclude that on instances that are currently tractable for the solver, there are not enough blocks such that a second random partition sufficiently improves the enumeration of compatible blocks. However, we can also observe that the trend is positive, i. e., the overhead of a second coloring is reduced more and more on harder instances.