Hof van 't, P. and Kaminski, M. and Paulusma, Daniel and Szeider, S. and Thilikos, D.M. (2010) 'On contracting graphs to fixed pattern graphs.', in 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. Berlin ; Heidelburg: Springer, pp. 503-514. Lecture notes in computer science. (5901).
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.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-11266-9_42|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2010|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|