Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Chaplick, S.; Fiala, J.; Hof, van 't P.; Paulusma, D.; Tesař, M.

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., & Tesař, M. (2015). Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science, 590, 86-95. https://doi.org/10.1016/j.tcs.2015.01.028

• Journal Article Type: Article
• Acceptance Date: Jan 16, 2015
• Publication Date: Jul 26, 2015
• Deposit Date: Jan 23, 2015
• Publicly Available Date: Jan 25, 2015
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 590
• Pages: 86-95
• DOI: https://doi.org/10.1016/j.tcs.2015.01.028
• Keywords: Computational complexity, Locally constrained graph homomorphisms, Bounded treewidth, Bounded degree.
• Public URL: https://durham-repository.worktribe.com/output/1413802