The complexity of locally injective homomorphisms |
| |
Authors: | Gary MacGillivray |
| |
Institution: | a Mathematics and Statistics, University of Victoria, PO BOX 3060 STN CSC, Victoria, B.C., Canada V8W 3R4 b Mathematics Department, Vancouver Island University, 900 Fifth Street, Nanaimo, B.C., Canada V9R 5S5 |
| |
Abstract: | A homomorphism f:G→H, from a digraph G to a digraph H, is locally injective if the restriction of f to N−(v) is an injective mapping, for each v∈V(G). The problem of deciding whether such an f exists is known as the injective H-colouring problem (INJ-HOMH). In this paper, we classify the problem INJ-HOMH as being either a problem in P or a problem that is NP-complete. This is done in the case where H is a reflexive digraph (i.e. H has a loop at every vertex) and in the case where H is an irreflexive tournament. A full classification in the irreflexive case seems hard, and we provide some evidence as to why this may be the case. |
| |
Keywords: | Digraph homomorphism Locally injective homomorphism Complexity Polynomial algorithm NP-completeness |
本文献已被 ScienceDirect 等数据库收录! |
|