Name
Abstract | ||
|---|---|---|
The problem takes as input two graphs and , and the task is to decide whether can be obtained from by a sequence of edge contractions. The and 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 -complete, even for certain graphs . We show that these problems can be solved in polynomial time for every fixed when the input graph is chordal. Our results can be considered tight, since these problems are known to be []-hard on chordal graphs when parameterized by the size of . To solve and , we define and use a generalization of the classic problem, where we require the vertices of each of the paths to be chosen from a specified set. We prove that this variant is -complete even when =2, but that it is polynomial-time solvable on chordal graphs for every fixed . Our algorithm for is based on another generalization of called , where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be -complete when =2, can be solved in polynomial time on chordal graphs even when 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-013-9748-5 | Algorithmica |
Keywords | Field | DocType |
Maximal Clique,Interval Graph,Input Graph,Disjoint Path,Tree Decomposition | Discrete mathematics,Combinatorics,Indifference graph,Interval graph,Vertex (graph theory),Chordal graph,Neighbourhood (graph theory),Cograph,Treewidth,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
69 | 3 | 0178-4617 |
Citations | PageRank | References |
4 | 0.43 | 24 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rémy Belmonte | 1 | 74 | 11.76 |
| Petr A. Golovach | 2 | 766 | 83.25 |
| Pinar Heggernes | 3 | 845 | 72.39 |
| Pim van 't Hof | 4 | 209 | 20.75 |
| Marcin Kaminski | 5 | 314 | 32.38 |
| Daniël Paulusma | 6 | 712 | 78.49 |