Contracting chordal graphs and bipartite graphs to paths and trees

Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque and Christophe Paul

Discrete Applied Mathematics, vol. 164, no. 2, pp. 444-449, 2014.

An extended abstract of this paper appeared in the proceedings of LAGOS 2011, the 6th Latin-American Algorithms, Graphs and Optimization Symposium (held on 28 March - 1 April in Bariloche, Argentina), Electronic Notes in Discrete Mathematics, vol. 37, pp. 87-92, 2011.


We study the following two graph modification problems: given a graph G and an integer k, decide whether G can be transformed into a tree or into a path, respectively, using at most k edge contractions. These problems, which we call Tree Contraction and Path Contraction, respectively, are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in O(n+m) and O(nm) time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs.