2012/12/01 by R. Crowston, G. Gutin, Crowston, R. +7
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1212.0117
arxiv created 2012/12/01 · arxiv updated 2012/12/04
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],\calT) 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.