Group Testing with Correlation under Edge-Faulty Graphs
Hesam Nikpey
Abstract:
In group testing problem, we want to find a set of defective items from a much larger set of size $n$. Traditionally, the state of the nodes are considered independent of each other, this might not be true in many applications though. For instance, in spreading a disease, the individuals who are in contact more often are more likely to be in the same state, i.e. be more correlated. In this work, we model correlation by a graph where each individual is represented as a node and their connections are represented as edges. A parameter $r$ represents the strength of the connections, where each edge is sampled with probability $r$. Then, the graph would be partitioned into connected components and nodes in the same component have the same state. For many graphs we show that we can utilize the correlation and obtain fewer tests compared to the traditional GP. The reduction in tests is rapidly increasing as the graphs get denser. More specifically, we present lower and upper bound on the number of tests for cycles, trees, grid, and SBM.