On the restricted homomorphism problem |
| |
| Authors: | Richard C Brewster Timothy Graves |
| |
| Institution: | 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 Y H, 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 等数据库收录！ |
|
