Parameterized Study of the Test Cover Problem

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 (log

n

 + 

k

)-

Test Cover

are W[1]-hard. Thus, it is unlikely that these problems are FPT.