Elsevier

Theoretical Computer Science

Volume 590, 26 July 2015, Pages 86-95
Theoretical Computer Science

Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

https://doi.org/10.1016/j.tcs.2015.01.028Get rights and content
Under an Elsevier user license
open archive

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.

Keywords

Computational complexity
Locally constrained graph homomorphisms
Bounded treewidth
Bounded degree

Cited by (0)

This paper is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), the Research Council of Norway (197548/F20), EPSRC (EP/G043434/1) and the Royal Society (JP100692). An extended abstract of it appeared in the Proceedings of FCT 2013 [10].

1

Supported by the ESF GraDR EUROGIGA grant as project GACR GIG/11/E023 and the NSERC grants of: K. Cameron and C. Hoàng (Wilfrid Laurier University), D. Corneil (University of Toronto), and P. Hell (Simon Fraser University).

2

Supported by MŠMT ČR grant LH12095 and GAČR grant P202/12/G061.