2012/09/28 by Robert Crowston, Gregory Gutin, Crowston, Robert +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Chromatin Dynamics #Ubiquitin and proteasome pathways #cs.DS
paper · pdf · doi:10.48550/arxiv.1209.6528
openalex publication_date 2012/09/28 · arxiv created 2013/02/15 · arxiv updated 2013/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the \sc 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 xi, xj, there exists an edge e ∈ E such that |xi,xj∩ e|=1. 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 \sc 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 \sc Test-r-Cover, the restriction of \sc 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 \sc 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 \lceil (2(n-1))/(r+1) \rceil on the minimum size of a test cover when the size of each edge is bounded by r. \sc 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 \sc Test-r-Cover has a test cover of size exactly (2(n-1))/(r+1).