Contracting chordal graphs and bipartite graphs to paths and trees

We study the following two graph modification problems: given a graph GG and an integer kk, decide whether GG can be transformed into a tree or into a path, respectively, using at most kk 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)O(n+m) and O(nm)O(nm) time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs.