Parameterizations of Test Cover with Bounded Test Sizes

In the Test Cover problem we are given a hypergraph H=(V,E) with |V|=n,|E|=m, and we assume that E is a test cover, i.e. for every pair of vertices (Formula Presented), there exists an edge (Formula Presented) such that (Formula Presented). The objective is to find a minimum subset of E which is a test cover. The problem is used for identification across many areas, and is NP-complete. From a parameterized complexity standpoint, many natural parameterizations of Test Cover are either W[1]-complete or have no polynomial kernel unless coNP⊆NP/poly, and thus are unlikely to be solveable efficiently. However, in practice the size of the edges is often bounded. In this paper we study the parameterized complexity of Test-r-Cover, the restriction of Test Cover in which each edge contains at most r≥2 vertices. In contrast to the unbounded case, we show that the following below-bound parameterizations of Test-r-Cover are fixed-parameter tractable with a polynomial kernel: (1) Decide whether there exists a test cover of size n-k, and (2) decide whether there exists a test cover of size m-k, where k is the parameter. In addition, we prove a new lower bound ⌈2(n-1)r+1⌉ on the minimum size of a test cover when the size of each edge is bounded by r. Test-r-Cover parameterized above this bound is unlikely to be fixed-parameter tractable; in fact, we show that it is para-NP-complete, as it is NP-hard to decide whether an instance of Test-r-Cover has a test cover of size exactly 2(n-1)r+1.