# Recent Advances in Positive-Instance Driven Graph Searching +
## 5 Color Coding Sieves  
The bottleneck in practical implementations of the presented algorithm is the enumeration of compatible blocks that can be glued (Line 22 and 23 in Figure 5). The same problem was observed in the positive-instance driven algorithms for treewidth [52] and treedepth [48]. Both used so called _block sieves_ to tackle this problem. These sieves are data structures based on set tries [82] allowing for an efficient enumeration over blocks that are _possible_ candidates. More precisely, if \(K\) is the set of already computed blocks and the algorithm from Figure 5 reaches Line 22 with a block \(C\), a block sieve shall efficiently enumerate a set \(K^{\prime}\subseteq K\) such that all \(C^{\prime}\in K\) for which the algorithm reaches Line 24 are contained in \(K^{\prime}\) while \(|K\setminus K^{\prime}|\) is maximized. Trivially, one could store \(K\) as list and just test for every element whether it is compatible (this is exactly what Figure 5 does). A block sieve improves this naive idea by storing the sets in a tree that represents intersections. Hence, while enumerating the output, one can prune some parts of the tree (of \(K\)) and, thus, has to consider only a subset of \(K^{\prime}\subseteq K\). [PERSON] presented this idea for the first time [52] and a more involved version was used by [PERSON] [48]. However, both implementations came with the drawback that they do _not_ provide any guarantee on how well they sieve. We provide a randomized data structure for which we can provide tight bounds for the probability that certain unnecessary blocks are pruned. Furthermore, we show how to derandomize this data structure using the well-known color coding technique and obtain an implementation of the block sieve data structure that correctly prunes _all_ of these blocks. Another disadvantage of set tries is the overhead introduced by managing a tree structure of sets compared to, say, storing the blocks in a simple list or array. During the development of our treedepth solver \(\mathsf{PID}^{\star}\) for PACE 2020, we actually observed that block sieves can negatively impact the performance of positive-instance driven solvers on instances of medium size [49]. In this section, we develop a randomized data structure that gives us the performance advantage of block sieves, reduces the overhead introduced by the set tries, and provides provable guarantees on the sieve quality. _Color coding sieves_ apply different filter strategies successively to divide the set of all blocks into smaller and smaller sets. These sets often become small enough to be stored in simple lists. Only if these lists become too large, we divide them into multiple lists via a random choice. If such a separation happens frequently, the data structure converges into a classical set trie. We assume a total order \(<\) on \(V\), that is, \(V=\{1,2,\ldots,n\}\). Furthermore, we denote the smallest vertex in a set \(C\subseteq V\) by \(\min(C)\). Observe that \(<\) implies a partial order \(\less\) on subgraphs where \(C_{1}\less\mathsf{C}_{2}\) if, and only if, \(\min(C_{1})<\min(C_{2})\). The _color coding sieve_ will be used to store the set \(\mathcal{R}(Q)=V(\operatorname{pit}(G,k))\), which, as before, consists of blocks \(C\). The first operation supported by our data structure is the _insertion_ operation that inserts a block \(C\) to the set represented by the data structure and is denoted by insert(\(C\)). The second operation is used to speed up Line 22 in Listing 5. For a fixed block \(C\), we have to enumerate all blocks \(C^{\prime}\) that (i) do _not_ intersect \(C\) (procedure intersect(\(C\), \(C^{\prime}\)) in Figure 6) and that (ii) satisfy \(|N_{G}(C\cup C^{\prime})|\leq k\) (procedure offer(\(C\), \(t\)) in Figure 6). Recall that two blocks intersect if \(C\cap C^{\prime}\
eq\emptyset\), \(N_{G}(C)\cap C^{\prime}\
eq\emptyset\) or \(C\cap N_{G}(C^{\prime})\
eq\emptyset\). **Definition 3**. : _A block \(C^{\prime}\) is compatible with respect to a block \(C\) if all of the following holds:_  
1.