Towards Optimal and Expressive Kernelization for d-Hitting Set
Towards Optimal and Expressive Kernelization for d-Hitting Set
复制标题
DOI：
10.1007/s00453-013-9774-3
复制
发表时间：
2011-12
期刊：
影响因子：
1.1
通讯作者：
René van Bevern
中科院分区：
文献类型：
--
作者：
René van Bevern
超图中的向日葵是一组两两相交于同一顶点集的超边。向日葵是多项式时间数据约简中的一个有用工具，它可以用于形式化为d-Hitting集的问题，即覆盖一个超图的所有超边（其基数由一个常数从上到下有界）的问题。此外，在故障诊断中，向日葵产生简洁的解释“高度缺陷的结构”。我们提供了一个线性时间算法，通过寻找向日葵，转换的d-Hitting集的实例到一个等价的实例，包括在最多O（kd）的超边和顶点。在参数化复杂度方面，我们给出了一个具有渐近最优大小（unless）的问题核，并提供了实验结果，证明了我们算法的实用性。最后，我们证明了顶点数可以减少到O（kd−1），并在O（k1.5d）时间内进行额外的处理-将向日葵技术与Abu-Khzam和Moser的问题核结合起来。
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 asd-Hitting Set, the problem of covering all hyperedges (whose cardinality is bounded from above by a constantd) of a hypergraph by at mostkvertices. 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 ofd-Hitting Setinto an equivalent instance comprising at mostO(kd) hyperedges and vertices. In terms of parameterized complexity, we show a problem kernel with asymptotically optimal size (unless) and provide experimental results that show the practical applicability of our algorithm.Finally, we show that the number of vertices can be reduced toO(kd−1) with additional processing inO(k1.5d) time—nontrivially combining the sunflower technique with problem kernels due to Abu-Khzam and Moser.