Towards optimal and expressive kernelization for d-hitting set

René Van Bevern

Результат исследования: Научные публикации в периодических изданияхстатья по материалам конференциирецензирование

6 Цитирования (Scopus)


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.

Язык оригиналаанглийский
Страницы (с-по)121-132
Число страниц12
ЖурналLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7434 LNCS
СостояниеОпубликовано - 6 сен 2012
Опубликовано для внешнего пользованияДа
Событие18th Annual International Computing and Combinatorics Conference, COCOON 2012 - Sydney, NSW, Австралия
Продолжительность: 20 авг 201222 авг 2012


Подробные сведения о темах исследования «Towards optimal and expressive kernelization for d-hitting set». Вместе они формируют уникальный семантический отпечаток (fingerprint).