Parameterized Study of the Test Cover Problem

Abstract

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, $\mathcal{T}$, of distinct subsets of these items called tests. We assume that $\mathcal{T}$ is a test cover, i.e., for each pair of items there is a test in $\mathcal{T}$ containing exactly one of these items. The objective is to find a minimum size subcollection of $\mathcal{T}$, which is still a test cover. The generic parameterized version of {\sc Test Cover} is denoted by $p(k,n,|\mathcal{T}|)$-{\sc Test Cover}. Here, we are given $([n],\mathcal{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,|\mathcal{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) $(|\mathcal{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.

Cited by in corpus (1)

• Parameterizations of Test Cover with Bounded Test Sizes