On contracting graphs to fixed pattern graphs

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

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, December). On contracting graphs to fixed pattern graphs. Presented at 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 36th Conference on Current Trends in Theory and Practice of Computer Science
• Publication Date: Jan 1, 2010
• Deposit Date: Oct 6, 2010
• Print ISSN: 0302-9743
• 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