On contracting graphs to fixed pattern graphs

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

doi:10.1007/978-3-642-11266-9_42

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 proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	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
Editors	Jan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, Bernhard Rumpe
Publisher	Springer
Pages	503-514
Number of pages	12
ISBN (Electronic)	978-3-642-11266-9
ISBN (Print)	978-3-642-11265-2
DOIs	https://doi.org/10.1007/978-3-642-11266-9_42
Publication status	Published - 2010
Externally published	Yes
Event	36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010 - Špindleruv Mlýn, Czech Republic Duration: 23 Jan 2010 → 29 Jan 2010 Conference number: 36

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5901

Conference

Conference	36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010
Abbreviated title	SOFSEM 2010
Country/Territory	Czech Republic
City	Špindleruv Mlýn
Period	23/01/10 → 29/01/10

Access to Document

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

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. https://doi.org/10.1007/978-3-642-11266-9_42

van 't Hof, Pim ; Kaminski, Marcin ; Paulusma, Daniël et al. / On contracting graphs to fixed pattern graphs. 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. editor / Jan van Leeuwen ; Anca Muscholl ; David Peleg ; Jaroslav Pokorný ; Bernhard Rumpe. Springer, 2010. pp. 503-514 (Lecture Notes in Computer Science).

@inproceedings{f32fdb5980bd4711a0c7d451512c1161,

title = "On contracting graphs to fixed pattern graphs",

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.",

author = "\{van 't Hof\}, Pim and Marcin Kaminski and Dani{\"e}l Paulusma and Stefan Szeider and Thilikos, \{Dimitrios M.\}",

year = "2010",

doi = "10.1007/978-3-642-11266-9\_42",

language = "English",

isbn = "978-3-642-11265-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "503--514",

editor = "Leeuwen, \{Jan van\} and Anca Muscholl and David Peleg and Jaroslav Pokorn{\'y} and Bernhard Rumpe",

booktitle = "SOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Ml{\'y}n, Czech Republic, January 23-29, 2010. Proceedings",

address = "Germany",

note = "36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, SOFSEM 2010 ; Conference date: 23-01-2010 Through 29-01-2010",

}

van 't Hof, P, Kaminski, M, Paulusma, D, Szeider, S & Thilikos, DM 2010, On contracting graphs to fixed pattern graphs. in JV 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. Lecture Notes in Computer Science, vol. 5901, Springer, pp. 503-514, 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, Špindleruv Mlýn, Czech Republic, 23/01/10. https://doi.org/10.1007/978-3-642-11266-9_42

On contracting graphs to fixed pattern graphs. / van 't Hof, Pim; Kaminski, Marcin; Paulusma, Daniël et al.
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. ed. / Jan van Leeuwen; Anca Muscholl; David Peleg; Jaroslav Pokorný; Bernhard Rumpe. Springer, 2010. p. 503-514 (Lecture Notes in Computer Science; Vol. 5901).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On contracting graphs to fixed pattern graphs

AU - van 't Hof, Pim

AU - Kaminski, Marcin

AU - Paulusma, Daniël

AU - Szeider, Stefan

AU - Thilikos, Dimitrios M.

N1 - Conference code: 36

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.

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

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

M3 - Conference contribution

SN - 978-3-642-11265-2

T3 - Lecture Notes in Computer Science

SP - 503

EP - 514

BT - 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

A2 - Leeuwen, Jan van

A2 - Muscholl, Anca

A2 - Peleg, David

A2 - Pokorný, Jaroslav

A2 - Rumpe, Bernhard

PB - Springer

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

Y2 - 23 January 2010 through 29 January 2010

ER -

van 't Hof P, Kaminski M, Paulusma D, Szeider S, Thilikos DM. On contracting graphs to fixed pattern graphs. In Leeuwen JV, Muscholl A, Peleg D, Pokorný J, Rumpe B, editors, 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. Springer. 2010. p. 503-514. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-11266-9_42

On contracting graphs to fixed pattern graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this