Group Testing on a Network

Abstract

Group testing---where multiple samples are tested together using a single test kit and individual tests are performed only for samples in positive groups---is a popular strategy to optimize the use of testing resources. We investigate how to effectively group samples for testing based on a transmission network. We formalize the group assembling problem as a graph partitioning problem, where the goal is to minimize the expected number of tests needed to screen the entire network. The problem is shown to be computationally hard and thus we focus on designing effective heuristics for it. Using realistic epidemic models on real contact networks, we show that our approaches save up to 33\% of resources---compared to the best baseline---at 4\% prevalence, are still effective at higher prevalence, and are robust to missing transmission data.