On contracting graphs to fixed pattern graphs

Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Stefan Szeider, Dimitrios M. Thilikos

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

5 Citations (Scopus)

Abstract

For a fixed graph H, the H-Contractibility problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. The computational complexity classification of this problem is still open. So far, H has a dominating vertex in all cases known to be polynomially solvable, whereas H does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-Contractibility is NP-complete. We also present a new class of graphs H for which H-Contractibility is polynomially solvable. Furthermore, we study the (H,v)-Contractibility problem, where v is a vertex of H. The input of this problem is a graph G and an integer k. The question is whether G is H-contractible such that the “bag” of G corresponding to v contains at least k vertices. We show that this problem is NP-complete whenever H is connected and v is not a dominating vertex of H.
Original languageEnglish
Title of host publicationSOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 23-29, 2010. Proceedings
EditorsJan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, Bernhard Rumpe
PublisherSpringer Singapore
Pages503-514
Number of pages12
ISBN (Electronic)978-3-642-11266-9
ISBN (Print)978-3-642-11265-2
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010 - Špindleruv Mlýn, Czech Republic
Duration: 23 Jan 201029 Jan 2010
Conference number: 36

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5901

Conference

Conference36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010
Abbreviated titleSOFSEM 2010
CountryCzech Republic
CityŠpindleruv Mlýn
Period23/01/1029/01/10

Fingerprint Dive into the research topics of 'On contracting graphs to fixed pattern graphs'. Together they form a unique fingerprint.

  • Cite this

    van 't Hof, P., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010). On contracting graphs to fixed pattern graphs. In J. V. Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, & B. Rumpe (Eds.), SOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 23-29, 2010. Proceedings (pp. 503-514). (Lecture Notes in Computer Science; Vol. 5901). Springer Singapore. https://doi.org/10.1007/978-3-642-11266-9_42