The complexity of graph contractions

A. Levin, Daniël Paulusma, Gerhard Woeginger

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

1 Citation (Scopus)

Abstract

For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. We continue a line of research that was started in 1987 by Brouwer & Veldman, and we determine the computational complexity of H-CONTRACTIBILITY for certain classes of pattern graphs. In particular, we pin-point the complexity for all graphs H with five vertices. Interestingly, in all cases that are known to be polynomially solvable, the pattern graph H has a dominating vertex, whereas in all cases that are known to be NP-complete, the pattern graph H does not have a dominating vertex.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers
EditorsH.L. Bodlaender
PublisherSpringer
Pages322-333
ISBN (Electronic)978-3-540-39890-5
ISBN (Print)978-3-540-20452-7
DOIs
Publication statusPublished - 2003
Event29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003 - Elspeet, Netherlands
Duration: 19 Jun 200321 Jun 2003
Conference number: 29

Publication series

NameLecture notes in computer science
Volume2880
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003
Abbreviated titleWG
CountryNetherlands
CityElspeet
Period19/06/0321/06/03

Keywords

  • METIS-213362

Fingerprint

Dive into the research topics of 'The complexity of graph contractions'. Together they form a unique fingerprint.

Cite this