Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree

Chaplick, S.; Fiala, J.; Hof, van 't P.; Paulusma, D.; Tesar, 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., & Tesar, M. (2013, December). Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree. Presented at Liverpool, UK, 19th International Symposium, FCT 2013

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Liverpool, UK
• Publication Date: Jan 1, 2013
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 14, 2015
• Print ISSN: 0302-9743
• 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