On the restricted homomorphism problem |
| |
Authors: | Richard C. Brewster Timothy Graves |
| |
Affiliation: | aDepartment of Mathematics and Statistics, Thompson Rivers University, PO Box 3010, Kamloops, BC, Canada, V2C 5N3 |
| |
Abstract: | The restricted homomorphism problem asks: given an input digraph G and a homomorphism g:G→Y, does there exist a homomorphism f:G→H? We prove that if H is hereditarily hard and YH, then is NP-complete. Since non-bipartite graphs are hereditarily hard, this settles in the affirmative a conjecture of Hell and Nešetřil. |
| |
Keywords: | Digraph homomorphism Restricted homomorphism Hereditary hardness Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|