TY - JOUR

T1 - Towards optimal and expressive kernelization for d-hitting set

AU - Van Bevern, René

PY - 2014/1/1

Y1 - 2014/1/1

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 (whose cardinality is bounded from above by a constant 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 ⊂/poly) and provide experimental results that show the practical applicability of our algorithm. Finally, 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 (whose cardinality is bounded from above by a constant 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 ⊂/poly) and provide experimental results that show the practical applicability of our algorithm. Finally, 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.

KW - Algorithm engineering

KW - Fault diagnosis

KW - Linear-time data reduction

KW - Parameterized algorithmics

KW - Sunflower lemma

KW - Vertex cover in hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=84904265803&partnerID=8YFLogxK

U2 - 10.1007/s00453-013-9774-3

DO - 10.1007/s00453-013-9774-3

M3 - Article

AN - SCOPUS:84904265803

VL - 70

SP - 129

EP - 147

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -