## Edge contractions in subclasses of chordal graphs

*Rémy Belmonte, Pinar Heggernes and Pim van 't Hof*

*Discrete Applied Mathematics*, vol. 160, no. 7-8, pp. 999-1010, 2012.

[__DOI__]
[__Preprint__]

A preliminary version of this paper appeared in the proceedings of TAMC 2011, the 8th Annual Conference on Theory and Applications of Models of Computation (to be held on May 23-25, 2010, Tokyo, Japan), *Lecture Notes in Computer Science*, vol. 6648, pp. 528-539, 2011.

[__DOI__]

This paper was also presented at the DIMAP Workshop on Combinatorics and Graph Theory (held on April 4-7, 2011 at the University of Warwick, UK).

[__Slides__]

### 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.