Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
verfasst von : Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van ’t Hof, Marcin Kamiński, Daniël Paulusma
Erschienen in: Algorithms and 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
The
k
-
Disjoint Paths
problem, which takes as input a graph
G
and
k
pairs of specified vertices (
s
i
,
t
i
), asks whether
G
contains
k
mutually vertex-disjoint paths
P
i
such that
P
i
connects
s
i
and
t
i
, for
i
= 1,…,
k
. We study a natural variant of this problem, where the vertices of
P
i
must belong to a specified vertex subset
U
i
for
i
= 1,…,
k
. In contrast to the original problem, which is polynomial-time solvable for any fixed integer
k
, we show that this variant is
NP
-complete even for
k
= 2. On the positive side, we prove that the problem becomes polynomial-time solvable for any fixed integer
k
if the input graph is chordal. We use this result to show that, for any fixed graph
H
, the problems
H
-
Contractibility
and
H
-
Induced Minor
can be solved in polynomial time on chordal graphs. These problems are to decide whether an input graph
G
contains
H
as a contraction or as an induced minor, respectively.