Cascaded Group Testing

In this paper, we introduce a variation of the group testing problem where each test is specified by an ordered subset of items and returns the first defective item in the specified order or returns null if there are no defectives. The goal is to identify a small set of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> defective items amongst a collection of size N, using as few tests as possible for perfect recovery. For the adaptive testing regime, we show that a simple scheme can find all defective items in at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> tests, which is optimal. For the non-adaptive setting, we first come up with a necessary and sufficient condition for any collection of tests to be feasible for recovering all the defectives. Using this, we show that any feasible non-adaptive strategy requires at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(K^{2})$</tex> tests. In terms of achievability, it is easy to show the existence of a feasible collection of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(K^{2}\log(N/K))$</tex> tests. We show via carefully constructed explicit designs that one can do significantly better for constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex>. While the cases <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K=1,2$</tex> are straightforward, the case <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K=3$</tex> is already non-trivial and we come up with an iterative design that is asymptotically optimal and requires <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta(\log \log N)$</tex>, tests. Note that this is in contrast to standard binary group testing, where at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(\log N)$</tex> tests are required. For constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K\geq 3$</tex>, our iterative design requires only poly(<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\log \log N$</tex>) tests.