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

G. Gutin*, G. Muciaccia, A. Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The input of the Test Cover problem consists of a set V of vertices, and a collection E={E1,.,Em} of distinct subsets of V, called tests. A test Eq separates a pair vi,vj of vertices if |{vi,vj}â̂©Eq|=1. A subcollection T⊆E is a test cover if each pair vi,vj of distinct vertices is separated by a test in T. 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 tests. Both parameterizations are known to be fixed-parameter tractable. We prove that none have a polynomial size kernel unless NP⊆coNP/poly. 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.

Original languageEnglish
JournalInformation Processing Letters
Volume113
Issue number4
Pages (from-to)123-126
ISSN0020-0190
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Algorithms
  • Fixed parameter tractability
  • Kernel
  • Test cover

Fingerprint

Dive into the research topics of '(Non)existence of polynomial kernels for the Test Cover problem'. Together they form a unique fingerprint.

Cite this