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 journalArticleAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)

Abstract

We study the following two graph modification problems: given a graph and an integer , decide whether can be transformed into a tree or into a path, respectively, using at most 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 and time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs.
Original languageEnglish
Pages (from-to)444-449
Number of pages6
JournalDiscrete applied mathematics
Volume164
Issue number2
DOIs
Publication statusPublished - 19 Feb 2014
Externally publishedYes

Fingerprint Dive into the research topics of 'Contracting chordal graphs and bipartite graphs to paths and trees'. Together they form a unique fingerprint.

Cite this