Menu
Let \(H\) and \(Y\) be fixed digraphs, and let \(h\) be a fixed homomorphism of \(H\) to \(Y\). The \emph{Homomorphism Factoring Problem with respect} to \((H, h, Y)\) is described as follows:
\text{HFP}(H, h, Y)
INSTANCE: A digraph \(G\) and a homomorphism \(g\) of \(G\) to \(Y\).
QUESTION: Does there exist a homomorphism \(f\) of \(G\) to \(H\) such that \(h \circ f = g\)? That is, can the given homomorphism \(g\) be factored into the composition of \(h\) and some homomorphism \(f\) of \(G\) to \(H\)?
We investigate the complexity of this problem and show that it differs from that of the \(H\)-colouring problem, i.e., the decision problem “is there a homomorphism of a given digraph \(G\) to the fixed digraph \(H\)?”, and of restricted versions of this problem. We identify directed graphs \(H\) for which any homomorphism factoring problem involving \(h\) is solvable in polynomial time. By contrast, we prove that for any fixed undirected graph \(Y\) which is not a path on at most four vertices, there exists a fixed undirected graph \(H\), which can be chosen to be either a tree or a cycle, and a fixed homomorphism \(h\) of \(H\) to \(Y\) such that \text{HFP}(H, h, Y) is NP-complete, and if \(Y\) is such a path then \text{HFP}(H, h, Y) is polynomial.