Hof P. van 't
On contracting graphs to fixed pattern graphs
't, Hof P. van; Kaminski, M.; Paulusma, D.; Szeider, S.; Thilikos, D. M.
Authors
M. Kaminski
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
S. Szeider
D. M. Thilikos
Contributors
Jan van Leeuwen
Editor
Anca Muscholl
Editor
David Peleg
Editor
Jaroslav Pokorný
Editor
Bernhard Rumpe
Editor
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). On contracting graphs to fixed pattern graphs. In J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, & B. Rumpe (Eds.), 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 (503-514). https://doi.org/10.1007/978-3-642-11266-9_42
Conference Name | 36th Conference on Current Trends in Theory and Practice of Computer Science |
---|---|
Conference Location | Špindleruv Mlýn, Czech Republic |
Publication Date | Jan 1, 2010 |
Deposit Date | Oct 6, 2010 |
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 |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search