### 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 Singapore |

Pages | 503-514 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-642-11266-9 |

ISBN (Print) | 978-3-642-11265-2 |

DOIs | |

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 | Czech Republic |

City | Špindleruv Mlýn |

Period | 23/01/10 → 29/01/10 |

## Fingerprint Dive into the research topics of 'On contracting graphs to fixed pattern graphs'. Together they form a unique fingerprint.

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