Back to Search
Start Over
Edge contractions in subclasses of chordal graphs
- Source :
- Discrete Applied Mathematics. (7-8):999-1010
- Publisher :
- Elsevier B.V.
-
Abstract
- Modifying a given graph to obtain another graph is a well-studied 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.
- Subjects :
- Block graph
Discrete mathematics
Graph modification algorithms
Threshold graph
Applied Mathematics
Symmetric graph
law.invention
Combinatorics
Pathwidth
law
Trivially perfect graph
Chordal graphs
Induced subgraph isomorphism
Line graph
Discrete Mathematics and Combinatorics
Edge contractions
Split graph
Mathematics
Distance-hereditary graph
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Issue :
- 7-8
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....263498889d4b5347526b8f63534b671d
- Full Text :
- https://doi.org/10.1016/j.dam.2011.12.012