# Recent Advances in Positive-Instance Driven Graph Searching +
## 5 Color Coding Sieves
### Optimizing Level-2 Sieves  
We have not yet specified the colorings used in level 2. In the following, we first consider randomized colorings and then make use of _color coding_ for derandomization. Using the guarantees provided by this technique, we obtain a provable running time bound for the level-2 sieve. We are interested in the probability that a block \(C^{\prime}\) with \(|N_{G}(C\cup C^{\prime})|>k\) is part of the output if we use random colorings. **Lemma 6**. : _Let \(\gamma=1\) and fix some blocks \(C\) and \(C^{\prime}\) with \(|N_{G}(C\cup C^{\prime})|>k\). If \(\mathsf{color}_{1}\) is chosen randomly, the probability that \(C^{\prime}\) is output by \(\mathsf{query}(C)\) is at most_  
\[1-\frac{k+1}{2^{k+1}}.\]  
Proof of Lemma 6.: Let \(\hat{k}=|N_{G}(C\cup C^{\prime})|\in\{k+1,\ldots,2k\}\) and let \(\mathsf{color}_{1}\) be a randomly sampled coloring. Note that \(C^{\prime}\) is output by \(\mathsf{query}(C)\) if, and only if, \(\beta(C)+\omega(C^{\prime})\leq k\), where we define \(\beta(C):=|\{\,v\in N_{G}(C)\mid\mathsf{color}(v)=\text{blue}\,\}\) as the number of blue neighbors and \(\omega(C)\) equivalently as the number of orange neighbors. A coloring is called _good_ if \(\beta(C)+\omega(C^{\prime})>k\) as it allows to discard \(C^{\prime}\). A vertex \(v\in N_{G}(C\cup C^{\prime})\) is _good_ if either \(\mathsf{color}(v)=\text{blue}\) and \(v\in N_{G}(C)\) or \(\mathsf{color}(v)=\text{orange}\) and \(v\in N_{G}(C^{\prime})\). Hence, a coloring is good if at least \(k+1\) vertices are good. Note that all vertices in \(N_{G}(C)\cap N_{G}(C^{\prime})\) are good (as each vertex is colored). In the following, we thus assume that \(N_{G}(C)\cap N_{G}(C^{\prime})=\emptyset\), which is the worst case. As each coloring occurs with probability \(2^{-k}\), the probability to hit a good coloring is then exactly  
\[\big{(}2^{\hat{k}}\big{)}^{-1}\sum_{i=\hat{k}+1}^{\hat{k}}\binom{\hat{k}}{i}.\]  
Hence, the probability of hitting a non-good coloring (and outputting \(C^{\prime}\)) is at most  
\[1-\frac{\sum_{i=\hat{k}+1}^{\hat{k}}\binom{\hat{k}}{i}}{2^{\hat{k}}}=\frac{ \sum_{i=0}^{k}\binom{\hat{k}}{i}}{2^{\hat{k}}}.\]  
Figure 7: A color coding sieve for the nine vertex graph shown on the bottom left with \(k=4\) and \(\gamma=1\). The three levels are illustrated as gray boxes and show the contained sieves of the next level—green pointers indicate which level-\(i\) sieve is shown, i. e., the level-2 sieve is \(S_{1}\) and the level-3 sieve is \(S_{1}[2]\) (all the other sieves are not shown). In the center, an insert of \(\{2,8\}\) is illustrated: the first sieve inserts it to \(S_{1}\), the level-2 sieve \(S_{1}\) inserts it to the level-3 sieve \(S_{1}[2]\) (other branches are not shown). The level-2 sieve uses the random partition shown on the graph, that is, \(\{2,8\}\) has two orange neighbors. The level-3 sieve \(S_{1}[2]\) is an ordinary list before the insert and becomes a trie after the insert, as a random split at vertex 8 occurs. On the right side of the figure, we see all sieves that we have to search through in order to answer the query \((\{3,4,5\})\). This term is maximized for \(\hat{k}=k+1\), as the denominator grows faster than the nominator. Hence, the probability to output \(C^{\prime}\) is at most  
\[\frac{\sum_{i=0}^{k}\binom{\hat{k}}{i}}{2^{\hat{k}}}\leq\frac{\sum_{i=0}^{k} \binom{\hat{k}+1}{i}}{2^{k+1}}=1-\frac{k+1}{2^{k+1}}.\qed\]  
If we choose all \(\gamma\) colorings randomly and independent, we obtain:  
**Corollary 2**. : _Fix some blocks \(C\) and \(C^{\prime}\) with \(|N_{G}(C\cup C^{\prime})|>k\). If \(\mathsf{color}_{1},\mathsf{color}_{2},\ldots,\mathsf{color}_{7}\) are chosen randomly and independent, the probability that \(C^{\prime}\) is output by query(\(C\)) is at most_  
\[(1-\frac{k+1}{2^{k+1}})^{\gamma}.\]  
We can now increase \(\gamma\) until the term \((1-\frac{k+1}{2^{k+1}})^{\gamma}\) is below a tolerable threshold.