[Question] SARS-CoV-2 pool-testing algorithm puzzle

According to this article, it’s possible to test a pool of up to (at least) 64 people for SARS-CoV-2 at once, and the test will say whether at least one person in the pool is positive. So, here’s the puzzle:

We have a large number N of people that need to be tested. Each has SARS-CoV-2 with probability P. (The cases of interest are P<5%, maybe even P<1%, see comment.) We can test any subset of the N (or maybe up to a maximum pool size S), with the test returning positive if at least person in the subset is positive. (Bonus: allow that the tests are imperfect, with a per-test false positive rate FPR and false negative rate FNR.)

Your mission is to develop a testing protocol, i.e. an algorithm for what tests to run in what order. The simplest example (proposed in that article linked above) would be: Test non-overlapping groups, and if the test is positive, test each individual within the group. But is there a better way?

Score your algorithm’s success on some combination of: (1) minimal total expected number of tests, (2) trying not to ask people for too many samples (lower priority on this one I think[1]), (3) false positive and false negative rates for individuals, (4) minimal serial time (i.e., minimal number of steps where we need results from step N to figure out what tests to run in step N+1).

(I’m not sure how to combine these criteria into a single score that reflects practical goals; if anyone knows, please comment. Or tell me if I’m leaving something out.)

Bonus: What if we have prior information, in the form of a N×N correlation matrix? (This could reflect the fact that for cohabitants /​ colleagues /​ neighbors, it’s likelier that both or neither have it.)


  1. ↩︎

    The swabbing process is mildly unpleasant, so other things equal, better to not require lots of swabs. I don’t know whether or not it’s possible to split the sample one swab and put it into multiple test-pools.