(Non-)existence of polynomial kernels for the Test Cover problem

(Non-)existence of polynomial kernels for the Test Cover problem

0.00 Avg rating0 Votes
Article ID: iaor2013787
Volume: 113
Issue: 4
Start Page Number: 123
End Page Number: 126
Publication Date: Feb 2013
Journal: Information Processing Letters
Authors: , ,
Keywords: graphs
Abstract:

The input of the Test Cover problem consists of a set V of vertices, and a collection E = { E 1 , , E m } equ1 of distinct subsets of V, called tests. A test E q equ2 separates a pair v i , v j equ3 of vertices if | { v i , v j } n E q | = 1 equ4. A subcollection T E equ5 is a test cover if each pair v i , v j equ6 of distinct vertices is separated by a test in T equ7. The objective is to find a test cover of minimum cardinality, if one exists. This problem is NP‐hard. We consider two parameterizations of the Test Cover problem with parameter k: (a) decide whether there is a test cover with at most k tests, (b) decide whether there is a test cover with at most | V | k equ8 tests. Both parameterizations are known to be fixed‐parameter tractable. We prove that none have a polynomial size kernel unless NP coNP / poly equ9. Our proofs use the cross‐composition method recently introduced by Bodlaender et al. (2011) and parametric duality introduced by Chen et al. (2005). The result for the parameterization (a) was an open problem (private communications with Henning Fernau and Jiong Guo, Jan.–Feb. 2012). We also show that the parameterization (a) admits a polynomial size kernel if the size of each test is upper‐bounded by a constant.

Reviews

Required fields are marked *. Your email address will not be published.