Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $V(D)$ that preserves the arcs, that is, if $uv$ is an arc of $G$, then $f(u)f(v)$ is an arc of $D$.)The class of $D$-COLORING problems is strongly connected to the Dichotomy Conjecture for CSPs stated by Feder and Vardi (accessible on citeseer).In this 2001 paper (accessible on the author's page, here), Feder proves a dichotomy theorem when $D$ is an oriented cycle (by oriented cycle I mean an undirected cycle where each edge is replaced by a single arc, that can be oriented arbitrarily), in other words, he shows that for any oriented cycle $D$, $D$-COLORING is either polynomial-time solvable or NP-complete.Unfortunately, Feder's classification is highly nontrivial and not explicit, as the complexity of many cases is related to the complexity of certain restricted variants of SAT that depend on the orientation. By looking at the paper, I have not been able to determine the answer to my question:Question: What is the smallest size of an oriented cycle $D$ such that $D$-COLORING is NP-complete?The answer might be stated somewhere in the literature, but I could not find it.Edit: Let me give more details on Feder's classification. Feder shows that any NP-complete oriented cycle must be balanced, that is, have the same number of arcs in both directions (hence it has even order). Then, consider the levels induced by the orientation (start to go around the cycle at an arbitrary vertex; if an arc goes right, you go up by 1, if an arc goes left, you go down by 1). Then, if there is at most one top-bottom run, it is polynomial. If there are at least 3 such runs and the cycle is a core, it is NP-complete. (In Andrs' example from the comments, there are three such runs, but the cycle is not a core.) The most tricky cases are those with two top-bottom runs. Some are hard, some polynomial, and Feder relates them to special SAT problems to obtain a dichotomy. I guess one could make a case-by-case analysis and see what kind of SAT problem it corresponds to...As an intermediate question: What is the smallest oriented cycle that has three top-bottom runs and is a core? Such an example would be NP-complete by the above discussion.
Complexity of digraph homomorphism to an oriented cycle
reference request;graph theory;np hardness;csp;homomorphism