Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437685 | Theoretical Computer Science | 2015 | 10 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Steven Chaplick, Jiří Fiala, Pim van 't Hof, Daniël Paulusma, Marek Tesař,