|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
(Non-)existence of Polynomial Kernels for the Test Cover Problem | | G. Gutin
; G. Muciaccia
; A. Yeo
; | | Date: |
19 Apr 2012 | | Abstract: | The input of the Test Cover problem consists of a set $V$ of vertices, and a
collection ${cal E}={E_1,..., E_m}$ of distinct subsets of $V$, called
tests. A test $E_q$ separates a pair $v_i,v_j$ of vertices if $|{v_i,v_j}cap
E_q|=1.$ A subcollection ${cal T}subseteq {cal E}$ is a test cover if each
pair $v_i,v_j$ of distinct vertices is separated by a test in ${cal T}$. The
objective is to find a test cover of minimum cardinality, if one exists. This
problem is NP-hard.
We consider two parameterizations 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 $NPsubseteq 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. | | Source: | arXiv, 1204.4368 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER