Edge contractions in subclasses of chordal graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

Abstract

Modifying a given graph to obtain another graph is a well-studied problem with applications in many fields. Given two input graphs G and H, the Contractibility problem is to decide whether H can be obtained from G 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 G is a trivially perfect graph and H 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 G and H are both trivially perfect graphs, and when G is a split graph and H is a threshold graph. If the graph H is fixed and only G is given as input, then the problem is called H-Contractibility. This problem is known to be NP-complete on general graphs already when H is a path on four vertices. We show that, for any fixed graph H, the H-Contractibility problem can be solved in polynomial time if the input graph G is a split graph.
Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings
EditorsMitsunori Ogihara, Jun Tarui
PublisherSpringer
Pages528-539
Number of pages12
ISBN (Electronic)978-3-642-20877-5
ISBN (Print)978-3-642-20876-8
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, Japan
Duration: 23 May 201125 May 2011
Conference number: 8

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6648

Conference

Conference8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
Abbreviated titleTAMC 2011
Country/TerritoryJapan
CityTokyo
Period23/05/1125/05/11

Fingerprint

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

Cite this