Skip to main content

Research Repository

Advanced Search

On contracting graphs to fixed pattern graphs

't, Hof P. van; Kaminski, M.; Paulusma, D.; Szeider, S.; Thilikos, D. M.

Authors

Hof P. van 't

M. Kaminski

S. Szeider

D. M. Thilikos



Contributors

Jan van Leeuwen
Editor

Anca Muscholl
Editor

David Peleg
Editor

Jaroslav Pokorný
Editor

Bernhard Rumpe
Editor

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.

Citation

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

Conference Name 36th Conference on Current Trends in Theory and Practice of Computer Science
Conference Location Špindleruv Mlýn, Czech Republic
Publication Date Jan 1, 2010
Deposit Date Oct 6, 2010
Publisher Springer Verlag
Pages 503-514
Series Title Lecture notes in computer science
Series Number 5901
Edition 36th
Book Title Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, Špindleruv Mlýn, Czech Republic, 23-29 January 2010 ; proceedings.
DOI https://doi.org/10.1007/978-3-642-11266-9_42
Public URL https://durham-repository.worktribe.com/output/1158590


You might also like



Downloadable Citations