S. Chaplick
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
Chaplick, S.; Fiala, J.; Hof, van 't P.; Paulusma, D.; Tesar, M.
Authors
Contributors
Leszek Gąsieniec
Editor
Frank Wolter
Editor
Abstract
A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even when G has pathwidth at most 5, 4 or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree.
Citation
Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesar, M. (2013). Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree. In L. Gąsieniec, & F. Wolter (Eds.), Fundamentals of computation theory : 19th International Symposium, FCT 2013, 19-21 August 2013, Liverpool, UK ; proceedings (121-132). https://doi.org/10.1007/978-3-642-40164-0_14
Conference Name | Liverpool, UK |
---|---|
Conference Location | 19th International Symposium, FCT 2013 |
Publication Date | Jan 1, 2013 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Jan 14, 2015 |
Pages | 121-132 |
Series Title | Lecture notes in computer science |
Series Number | 8070 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Fundamentals of computation theory : 19th International Symposium, FCT 2013, 19-21 August 2013, Liverpool, UK ; proceedings. |
ISBN | 9783642401633 |
DOI | https://doi.org/10.1007/978-3-642-40164-0_14 |
Public URL | https://durham-repository.worktribe.com/output/1153164 |
Files
Accepted Conference Proceeding
(382 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-40164-0_14
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
An algorithmic framework for locally constrained homomorphisms
(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
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