The
Contractibility problem takes as input two graphs
G and
H, and the task is to decide whether
H can be obtained from
G by a sequence of edge contractions. The
Induced Minor and
Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are
NP-complete, even for certain
fixed graphs
H. We show that these problems can be solved in polynomial time for every fixed
H when the input graph
G is chordal. Our results can be considered tight, since these problems are known to be
W[
1]-hard on chordal graphs when parameterized by the size of
H. To solve
Contractibility and
Induced Minor, we define and use a generalization of the classic
Disjoint Paths problem, where we require the vertices of each of the
k paths to be chosen from a specified set. We prove that this variant is
NP-complete even when
k=2, but that it is polynomial-time solvable on chordal graphs for every fixed
k. Our algorithm for
Induced Topological Minor is based on another generalization of
Disjoint Paths called
Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be
NP-complete when
k=2, can be solved in polynomial time on chordal graphs even when
k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.
相似文献