Towards optimal and expressive kernelization for d-hitting set. / Van Bevern, René.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 7434 LNCS, 06.09.2012, p. 121-132.Research output: Contribution to journal › Conference article › peer-review
}
TY - JOUR
T1 - Towards optimal and expressive kernelization for d-hitting set
AU - Van Bevern, René
PY - 2012/9/6
Y1 - 2012/9/6
N2 - A sunflower in a hypergraph is a set of hyperedges pairwise intersecting in exactly the same vertex set. Sunflowers are a useful tool in polynomial-time data reduction for problems formalizable as d-Hitting Set, the problem of covering all hyperedges (of cardinality at most d) of a hypergraph by at most k vertices. Additionally, in fault diagnosis, sunflowers yield concise explanations for "highly defective structures". We provide a linear-time algorithm that, by finding sunflowers, transforms an instance of d-Hitting Set into an equivalent instance comprising at most O(k d) hyperedges and vertices. In terms of parameterized complexity, we show a problem kernel with asymptotically optimal size (unless coNP ⊆ NP/poly). We show that the number of vertices can be reduced to O(k d-1) with additional processing in O(k 1.5d) time-nontrivially combining the sunflower technique with problem kernels due to Abu-Khzam and Moser.
AB - A sunflower in a hypergraph is a set of hyperedges pairwise intersecting in exactly the same vertex set. Sunflowers are a useful tool in polynomial-time data reduction for problems formalizable as d-Hitting Set, the problem of covering all hyperedges (of cardinality at most d) of a hypergraph by at most k vertices. Additionally, in fault diagnosis, sunflowers yield concise explanations for "highly defective structures". We provide a linear-time algorithm that, by finding sunflowers, transforms an instance of d-Hitting Set into an equivalent instance comprising at most O(k d) hyperedges and vertices. In terms of parameterized complexity, we show a problem kernel with asymptotically optimal size (unless coNP ⊆ NP/poly). We show that the number of vertices can be reduced to O(k d-1) with additional processing in O(k 1.5d) time-nontrivially combining the sunflower technique with problem kernels due to Abu-Khzam and Moser.
UR - http://www.scopus.com/inward/record.url?scp=84864966458&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32241-9_11
DO - 10.1007/978-3-642-32241-9_11
M3 - Conference article
AN - SCOPUS:84864966458
VL - 7434 LNCS
SP - 121
EP - 132
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
SN - 0302-9743
T2 - 18th Annual International Computing and Combinatorics Conference, COCOON 2012
Y2 - 20 August 2012 through 22 August 2012
ER -
ID: 22341237