Parameterized Study of the Test Cover Problem

Abstract

In this paper 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 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 Test Cover is denoted by $p(k,n,|{\cal T}|)$-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 Test Cover and obtain the following:

(a) k-Test Cover, and (n − k)-Test Cover are fixed-parameter tractable (FPT), i.e., these problems can be solved by algorithms of runtime $f(k)\cdot poly(n,|{\cal T}|)$, where f(k) is a function of k only.

(b) $(|{\cal T}|-k)$-Test Cover and (logn + k)-Test Cover are W[1]-hard. Thus, it is unlikely that these problems are FPT.