TY - GEN

T1 - On contracting graphs to fixed pattern graphs

AU - Van'T Hof, Pim

AU - Kamiński, Marcin

AU - Paulusma, Daniël

AU - Szeider, Stefan

AU - Thilikos, Dimitrios M.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77249168752&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77249168752&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-11266-9_42

DO - 10.1007/978-3-642-11266-9_42

M3 - Conference contribution

AN - SCOPUS:77249168752

SN - 3642050050

SN - 9783642050053

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 503

EP - 514

BT - SOFSEM 2010

T2 - 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010

Y2 - 23 January 2010 through 29 January 2010

ER -