Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Steven Chaplick, Jiří Fiala, Pim van 't Hof, Daniël Paulusma and Marek Tesař

Theoretical Computer Science, vol. 590, pp. 86-95, 2015.

A preliminary version of this paper appeared in the proceedings of FCT 2013, 19th International Symposium on Fundamentals of Computation Theory (held on August 19-21, 2013 in Liverpool, United Kingdom), Lecture Notes in Computer Science, vol. 8070, pp. 121-132, 2013.


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 in the restricted case where 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.