Bounded Tree-Width and CSP-Related Problems
2007 (English)In: Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings / [ed] Takeshi Tokuyama, Springer Berlin/Heidelberg, 2007, 632-643 p.Chapter in book (Refereed)
We study the complexity of structurally restricted homomorphism and constraint satisfaction problems. For every class of relational structures C , let LHom be the problem of deciding whether a structure A Î CA has a homomorphism to a given arbitrary structure B, when each element in A is only allowed a certain subset of elements of B as its image. We prove, under a certain complexity-theoretic assumption, that this list homomorphism problem is solvable in polynomial time if and only if all structures in C have bounded tree-width. The result is extended to the connected list homomorphism, edge list homomorphism, minimum cost homomorphism and maximum solution problems. We also show an inapproximability result for the minimum cost homomorphism problem.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2007. 632-643 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 4835
Computational complexity - constraint satisfaction - homomorphism - relational structure - inapproximability
IdentifiersURN: urn:nbn:se:liu:diva-40859DOI: 10.1007/978-3-540-77120-3_55Local ID: 54335ISBN: 978-3-540-77118-0ISBN: 3-540-77118-2ISBN: e-978-3-540-77120-3OAI: oai:DiVA.org:liu-40859DiVA: diva2:261708