Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Polynomial Kernels for Proper Interval Completion and Related Problems
verfasst von : Stéphane Bessy, Anthony Perez
Erschienen in: Fundamentals of Computation Theory
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
Given a graph
G
= (
V
,
E
) and a positive integer
k
, the
Proper Interval Completion
problem asks whether there exists a set
F
of at most
k
pairs of (
V
×
V
) ∖
E
such that the graph
H
= (
V
,
E
∪
F
) is a proper interval graph. The
Proper Interval Completion
problem finds applications in molecular biology and genomic research [11]. First announced by Kaplan, Tarjan and Shamir in FOCS ’94, this problem is known to be FPT [11], but no polynomial kernel was known to exist. We settle this question by proving that
Proper Interval Completion
admits a kernel with
O
(
k
5
) vertices. Moreover, we prove that a related problem, the so-called
Bipartite Chain Deletion
problem admits a kernel with
O
(
k
2
) vertices, completing a previous result of Guo [10].