Positively Correlated Samples Save Pooled Testing Costs

The group testing approach, which achieves significant cost reduction over the individual testing approach, has received a lot of interest lately for massive testing of COVID-19. Many studies simply assume samples mixed in a group are independent. However, this assumption may not be reasonable for a contagious disease like COVID-19. Specifically, people within a family tend to infect each other and thus are likely to be positively correlated. By exploiting positive correlation, we make the following two main contributions. One is to provide a rigorous proof that further cost reduction can be achieved by using the Dorfman two-stage method when samples within a group are positively correlated. The other is to propose a hierarchical agglomerative algorithm for pooled testing with a social graph, where an edge in the social graph connects frequent social contacts between two persons. Such an algorithm leads to notable cost reduction (roughly 20-35%) compared to random pooling when the Dorfman two-stage algorithm is applied.