An Efficient Algorithm for Group Testing with Runlength Constraints

Abstract

In this paper, we provide an efficient algorithm to construct almost optimal $(k,n,d)$-superimposed codes with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t\times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. These combinatorial structures were introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. By using Moser and Tardos' constructive version of the Lovász Local Lemma, we provide an efficient randomized Las Vegas algorithm of complexity $\hat{I}˜(t{n}^2)$ for the construction of $(k,n,d)$-superimposed codes of length $t=O(dk\log n+k^2\log n)$. We also show that the length of our codes is shorter, for $n$ sufficiently large, than that of the codes whose existence was proved in [1].

Accepted for publication in Discrete Applied Mathematics