Name
Abstract | ||
|---|---|---|
Modifying a given graph to obtain another graph is a wellstudied problem with applications in many fields. Given two input graphs G and H, the Contractibility problem is to decide whether H can be obtained from G by a sequence of edge contractions. This problem is known to be NP-complete already when both input graphs are trees of bounded diameter. We prove that CONTRACTIBILITY can be solved in polynomial time when G is a trivially perfect graph and H is a threshold graph, thereby giving the first classes of graphs of unbounded treewidth and unbounded degree on which the problem can be solved in polynomial time. We show that this polynomial-time result is in a sense tight, by proving that Contractibility is NP-complete when G and H are both trivially perfect graphs, and when G is a split graph and H is a threshold graph. If the graph H is fixed and only G is given as input, then the problem is called H-CONTRACTIBILITY. This problem is known to be NP-complete on general graphs already when H is a path on four vertices. We show that, for any fixed graph H, the H-CONTRACTIBILITY problem can be solved in polynomial time if the input graph G is a split graph. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2011.12.012 | Discrete Applied Mathematics |
Keywords | Field | DocType |
induced subgraph isomorphism | Discrete mathematics,Block graph,Combinatorics,Line graph,Threshold graph,Distance-hereditary graph,Trivially perfect graph,Symmetric graph,Pathwidth,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
160 | 7-8 | 0166-218X |
Citations | PageRank | References |
15 | 0.80 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rémy Belmonte | 1 | 74 | 11.76 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Pim van 't Hof | 3 | 209 | 20.75 |