Computer Science – Discrete Mathematics
Scientific paper
2011-12-10
Computer Science
Discrete Mathematics
12 pages, 2 figures, yet unrefereed preprint
Scientific paper
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 theory, we show a problem kernel with asymptotically optimal size (unless coNP in 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 a known problem kernel that uses crown reductions.
No associations
LandOfFree
Towards Optimal and Expressive Kernelization for d-Hitting Set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Towards Optimal and Expressive Kernelization for d-Hitting Set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards Optimal and Expressive Kernelization for d-Hitting Set will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-306699