Contracting chordal graphs and bipartite graphs to paths and trees

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

Research output: Contribution to journalConference articleAcademicpeer-review

10 Citations (Scopus)


Some of the most well studied problems in algorithmic graph theory deal with modifying a graph into an acyclic graph or into a path, using as few operations as possible. In Feedback Vertex Set and Longest Induced Path, the only allowed operation is vertex deletion, and in Spanning Tree and Longest Path, only edge deletions are permitted. We study the edge contraction variant of these problems: given a graph G and an integer k, decide whether G can be transformed into an acyclic graph or into a path using at most k edge contractions. Both problems are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in and time, respectively. On the negative side, both problems remain NP-complete when restricted to bipartite input graphs.
Original languageEnglish
Pages (from-to)87-92
Number of pages6
JournalElectronic notes in discrete mathematics
Publication statusPublished - 2011
Externally publishedYes
Event6th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2011 - Hotel Edelweiss, Bariloche, Argentina
Duration: 28 Mar 20111 Apr 2011
Conference number: 6

Cite this