We carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the {sc Test Cover} problem we are given a set $[n]={1,...,n}$ of items together with a collection, $cal T$, of distinct subsets of these items called tests. We assume that $cal T$ is a test cover, i.e., for each pair of items there is a test in $cal T$ containing exactly one of these items. The objective is to find a minimum size subcollection of $cal T$, which is still a test cover. The generic parameterized version of {sc Test Cover} is denoted by $p(k,n,|{cal T}|)$-{sc Test Cover}. Here, we are given $([n],cal{T})$ and a positive integer parameter $k$ as input and the objective is to decide whether there is a test cover of size at most $p(k,n,|{cal T}|)$. We study four parameterizations for {sc Test Cover} and obtain the following: (a) $k$-{sc Test Cover}, and $(n-k)$-{sc Test Cover} are fixed-parameter tractable (FPT). (b) $(|{cal T}|-k)$-{sc Test Cover} and $(log n+k)$-{sc Test Cover} are W[1]-hard. Thus, it is unlikely that these problems are FPT.
Download