Sequential Group Testing with Graph Constraints

In conventional group testing, the goal is to detect a small subset of defecting items $\mathcal{D}$ in a large population $\mathcal{N}$ by grouping \textit{arbitrary} subset of $\mathcal{N}$ into different pools. The result of each group test $\mathcal{T}$ is a binary output depending on whether the group contains a defective item or not. The main challenge is to minimize the number of pools required to identify the set $\mathcal{D}$. Motivated by applications in network monitoring and infection propagation, we consider the problem of group testing with graph constraints. As opposed to conventional group testing where \textit{any} subset of items can be pooled, here a test is admissible if it induces a connected subgraph $H\subset G$. In contrast to the non-adaptive pooling process used in previous work, we first show that by exploiting an adaptive strategy, one can dramatically reduce the number of tests. More specifically, for \textit{any} graph $G$, we devise a 2-approximation algorithm (and hence order optimal) that locates the set of defective items $\mathcal{D}$. To obtain a good compromise between adaptive and non-adaptive strategies, we then devise a multi-stage algorithm. In particular, we show that if the set of defective items are uniformly distributed, then an $l$-stage pooling strategy can identify the defective set in $O(l\cdot|D|\cdot |\mathcal{N}|^{1/l})$ tests, on the average. In particular, for $l=\log(|\mathcal{N}|)$ stages, the number of tests reduces to $4|\mathcal{D}|\log(|\mathcal{N}|)$, which in turn is order optimum.