Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Even Faster Algorithm for Set Splitting!
verfasst von : Daniel Lokshtanov, Saket Saurabh
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In
p
-Set Splitting
we are given a universe
U
, a family
$\cal F$
of subsets of
U
and a positive integer
k
and the objective is to find a partition of
U
into
W
and
B
such that there are at least
k
sets in
$\cal F$
that have non-empty intersection with both
B
and
W
. In this paper we study
p
-Set Splitting
from kernelization and algorithmic view points. Given an instance
$(U,{\cal F},k)$
of
p
-Set Splitting
, our kernelization algorithm obtains an equivalent instance with at most 2
k
sets and
k
elements in polynomial time. Finally, we give a fixed parameter tractable algorithm for
p
-Set Splitting
running in time
O
(1.9630
k
+
N
), where
N
is the size of the instance. Both our kernel and our algorithm improve over the best previously known results. Our kernelization algorithm utilizes a classical duality theorem for a connectivity notion in hypergraphs. We believe that the duality theorem we make use of, will turn out to be an important tool from combinatorial optimization in obtaining kernelization algorithms.