Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 129-147 |
Number of pages | 19 |
Journal | Algorithmica |
Volume | 70 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Externally published | Yes |
Keywords
- Algorithm engineering
- Fault diagnosis
- Linear-time data reduction
- Parameterized algorithmics
- Sunflower lemma
- Vertex cover in hypergraphs