Edge contractions in subclasses of chordal graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)
3 Downloads (Pure)

Abstract

Modifying a given graph to obtain another graph is a well-studied problem with applications in many fields. Given two input graphs and , the Contractibility problem is to decide whether can be obtained from 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 is a trivially perfect graph and 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 and are both trivially perfect graphs, and when is a split graph and is a threshold graph. If the graph is fixed and only is given as input, then the problem is called -Contractibility. This problem is known to be NP-complete on general graphs already when is a path on four vertices. We show that, for any fixed graph , the -Contractibility problem can be solved in polynomial time if the input graph is a split graph.

Original languageEnglish
Pages (from-to)999-1010
Number of pages12
JournalDiscrete applied mathematics
Volume160
Issue number7-8
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'Edge contractions in subclasses of chordal graphs'. Together they form a unique fingerprint.

Cite this