Advertisement
Published in:
2011 | OriginalPaper | Chapter
Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
Authors : Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van ’t Hof, Marcin Kamiński, Daniël Paulusma
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.