<p>There recently has been some activity in this area. We wrote a program to determine the smallest NP-complete oriented trees, the smallest ones have 20 vertices. More details can be found here <a href="https://arxiv.org/abs/2205.07528" rel="nofollow noreferrer">https://arxiv.org/abs/2205.07528</a>.</p>
<p>I used the same program to find the smallest NP-complete oriented cycle. It has 26 vertices and it is also the smallest oriented cycle without a majority polymorphism:</p>
<p><a href="https://i.sstatic.net/6iT8j.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6iT8j.png" alt="enter image description here" /></a></p>
<p>There is only one other NP-hard oriented cycle with 26 vertices and it is just the above one with all edges reversed.</p>
<p>Could you verify with the top-bottom run (not sure what the definition is) criterion that this cycle is NP-hard?</p>

CC BY-SA 4.0
2022-07-15T08:27:21.630Z
Great! This cycle has 2 top-bottom runs. Thus it is in the "difficult zone": one needs to understand Feder's paper and analyze the SAT-problem that is equivalent to this cycle problem.
Florent Foucaud
CC BY-SA 4.0
2022-07-15T08:28:09.703Z
Is this the only example on 26 vertices that your programme has found?
Florent Foucaud
CC BY-SA 4.0
2022-07-15T09:20:13.553Z
There is one other cycle: just reverse all edges. These 2 cycles are the only hard ones with 26 vertices.
Florian
CC BY-SA 4.0
2022-07-15T07:13:07.323Z
2022-07-15T11:03:30.617Z
2022-07-15T11:03:30.617Z
Florian
<p>For the intermediate question (a core with three top-bottom runs), how about this?</p>

<p>Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:</p>

<ul>
<li>There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.</li>
<li>If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$. </li>
</ul>

<p>However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. This has the required top-bottom runs and is a core (see below). By the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.</p>

<p>To convince ourselves that this is a core, let's first name the vertices ($v_1,\ldots,v_{36}$). The bottom (i.e. level $0$) vertices are $v_1,v_{13},v_{25}$. Any homomorphism $\varphi$ from $D$ to a subgraph must preserve levels, and in particular $\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$; modulo the obvious automorphism $v_i\mapsto v_{i+12}$, it is enough to consider the case $\varphi(v_1)=v_1$. Consider the neighbourhood of $v_1$ in $D$ (annotated with levels):</p>

<p>$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$</p>

<p>Starting with $\varphi(v_1)=v_1$, we have $\varphi(v_2)\in\{v_{36},v_2\}$. But if $\varphi(v_2)=v_{36}$, then $\varphi(v_3)=v_{35}$, and we have no possible value for $\varphi(v_4)$. We get $\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$. Next $\varphi(v_5)\in\{v_3,v_5\}$, but for $\varphi(v_5)=v_3$ we get $\varphi(v_6)=v_4$, with no possible value for $\varphi(v_7)$. So $\varphi$ must be the identity on the entire run $v_1\to\ldots\to v_7$, and by repeating the same argument for the remaining runs, the same is true on all of $D$. In particular, $\varphi$ does not map $D$ onto a proper subgraph.</p>

CC BY-SA 3.0
2016-02-25T21:42:21.880Z
This same analysis shows that all balanced oriented cycles with two runs that are cores have length at least 24, right? So that gives a lower bound on the answer to the main problem.
David Eppstein
CC BY-SA 3.0
2016-02-26T00:40:13.597Z
Yes, good point.
Klaus Draeger
CC BY-SA 3.0
2016-02-26T18:01:12.937Z
Great, thanks, this is very helpful! Can we convince ourselves by hand that this is a core? (note that there is a polynomial-time algorithm to check if an oriented cycle $D$ is a core: create the set of $|V(D)|$ oriented sub-paths $\{D-a$ such that $a$ is an arc of $D\}$, and then check if $D$ maps to any of these paths; this can be done in polytime, see Gutjahr et al: http://www.sciencedirect.com/science/article/pii/0166218X9290294K)
Florent Foucaud
CC BY-SA 3.0
2016-02-27T15:08:01.097Z
@FlorentFoucaud I've added a bit showing that $D$ is a core.
Klaus Draeger
CC BY-SA 3.0
2016-02-25T16:26:36.797Z
2016-02-27T15:06:34.183Z
2016-02-27T15:06:34.183Z
Klaus Draeger
<p>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$.)</p>

<p>The class of $D$-COLORING problems is strongly connected to the Dichotomy Conjecture for CSPs <a href="http://dx.doi.org/10.1137/S0097539794266766">stated by Feder and Vardi</a> (accessible on <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.123.7882">citeseer</a>).</p>

<p>In <a href="http://dx.doi.org/10.1137/S0895480199383353">this 2001 paper</a> (accessible on the author's page, <a href="http://theory.stanford.edu/~tomas/oriented.ps">here</a>), Feder proves a dichotomy theorem when $D$ is an oriented cycle (by <em>oriented cycle</em> 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.</p>

<p>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:</p>

<blockquote>
  <p><b>Question:</b> What is the smallest size of an oriented cycle $D$ such that $D$-COLORING is NP-complete?</p>
</blockquote>

<p>The answer might be stated somewhere in the literature, but I could not find it.</p>

<hr>

<p><b>Edit:</b> 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 András' 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...</p>

<p>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.</p>

CC BY-SA 3.0
2016-02-19T00:31:22.063Z
I don't recall a quick answer in the literature (perhaps Barnaby Martin or Florent Madelaine would know).  However, the size is at most 6 vertices and 6 directed edges, since one can reduce $K_3$-Colouring to $D$-Colouring for a six-vertex digraph $D$ by replacing each undirected edge in the graphs by two arcs pointing to a new vertex between its endpoints.
András Salamon
CC BY-SA 3.0
2016-02-19T12:24:42.673Z
Thanks András. However, I think the answer must be larger because the core of this example is simply a digraph with a unique arc, which is polynomial-time solvable...
Florent Foucaud
CC BY-SA 3.0
2016-02-19T15:16:49.793Z
You are right, the construction I proposed is too simple.
András Salamon
CC BY-SA 3.0
2016-02-19T17:36:18.300Z
I asked Florent Madelaine and Barnaby Martin, but they don't know the answer directly, although they seem to be interested :-) My colleague asked Feder by email last week, but he did not reply (yet).
Florent Foucaud
CC BY-SA 3.0
2016-02-19T18:05:20.063Z
My second impulse was to use a rigidified version of the triangle.  However, with the rigidity gadget from Chvátal et al. (JCT 1971) the rigidified triangle then seems to require a number of vertices that is at least 9v+36, if the input graph has v vertices, and it is not clear how to modify these gadgets to paths.  Perhaps one could instead use a rigid directed path to replace each edge, but it is not clear to me how to do that while retaining the ability to map any edge of the graph to any edge of the triangle (but nowhere else), since the obvious way to do it is to require symmetry.
András Salamon
<reference-request><graph-theory><np-hardness><csp><homomorphism>
Complexity of digraph homomorphism to an oriented cycle
Florent Foucaud
# Complexity of digraph homomorphism to an oriented cycle

(Asked by: username_0 on 2016-02-16)

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](http://dx.doi.org/10.1137/S0097539794266766) (accessible on [citeseer](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.123.7882)).

In [this 2001 paper](http://dx.doi.org/10.1137/S0895480199383353) (accessible on the author's page, [here](http://theory.stanford.edu/~tomas/oriented.ps)), 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 András' 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.

**Tags:** reference-request, graph-theory, np-hardness, csp, homomorphism
> **Comments:**
> **username_1**: I don't recall a quick answer in the literature (perhaps Barnaby Martin or Florent Madelaine would know).  However, the size is at most 6 vertices and 6 directed edges, since one can reduce $K_3$-Colouring to $D$-Colouring for a six-vertex digraph $D$ by replacing each undirected edge in the graphs by two arcs pointing to a new vertex between its endpoints.  
> **username_0**: Thanks András. However, I think the answer must be larger because the core of this example is simply a digraph with a unique arc, which is polynomial-time solvable...  
> **username_1**: You are right, the construction I proposed is too simple.  
> **username_0**: I asked Florent Madelaine and Barnaby Martin, but they don't know the answer directly, although they seem to be interested :-) My colleague asked Feder by email last week, but he did not reply (yet).  
> **username_1**: My second impulse was to use a rigidified version of the triangle.  However, with the rigidity gadget from Chvátal et al. (JCT 1971) the rigidified triangle then seems to require a number of vertices that is at least 9v+36, if the input graph has v vertices, and it is not clear how to modify these gadgets to paths.  Perhaps one could instead use a rigid directed path to replace each edge, but it is not clear to me how to do that while retaining the ability to map any edge of the graph to any edge of the triangle (but nowhere else), since the obvious way to do it is to require symmetry.  

---

## 2 answers

### Answer by username_2 on 2022-07-15. Score: 4 | Accepted answer

There recently has been some activity in this area. We wrote a program to determine the smallest NP-complete oriented trees, the smallest ones have 20 vertices. More details can be found here <https://arxiv.org/abs/2205.07528>.

I used the same program to find the smallest NP-complete oriented cycle. It has 26 vertices and it is also the smallest oriented cycle without a majority polymorphism:

[![enter image description here](https://i.sstatic.net/6iT8j.png)](https://i.sstatic.net/6iT8j.png)

There is only one other NP-hard oriented cycle with 26 vertices and it is just the above one with all edges reversed.

Could you verify with the top-bottom run (not sure what the definition is) criterion that this cycle is NP-hard?

> **Comments:**
> **username_0**: Great! This cycle has 2 top-bottom runs. Thus it is in the "difficult zone": one needs to understand Feder's paper and analyze the SAT-problem that is equivalent to this cycle problem.  
> **username_0**: Is this the only example on 26 vertices that your programme has found?  
> **username_2**: There is one other cycle: just reverse all edges. These 2 cycles are the only hard ones with 26 vertices.  

---

### Answer by username_3 on 2016-02-25. Score: 5

For the intermediate question (a core with three top-bottom runs), how about this?

Some notation: I will be describing runs by words in $\{l,r\}^\*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:

* There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.
* If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$.

However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. This has the required top-bottom runs and is a core (see below). By the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.

To convince ourselves that this is a core, let's first name the vertices ($v\_1,\ldots,v\_{36}$). The bottom (i.e. level $0$) vertices are $v\_1,v\_{13},v\_{25}$. Any homomorphism $\varphi$ from $D$ to a subgraph must preserve levels, and in particular $\varphi(v\_1)\in\{v\_1,v\_{13},v\_{25}\}$; modulo the obvious automorphism $v\_i\mapsto v\_{i+12}$, it is enough to consider the case $\varphi(v\_1)=v\_1$. Consider the neighbourhood of $v\_1$ in $D$ (annotated with levels):

$v\_{34}(1)\to v\_{35}(2)\leftarrow v\_{36}(1)\leftarrow v\_1(0)\to v\_2(1)\to v\_3(2)\to v\_4(3)\leftarrow v\_5(2)\to v\_6(3)\to v\_7(4)$

Starting with $\varphi(v\_1)=v\_1$, we have $\varphi(v\_2)\in\{v\_{36},v\_2\}$. But if $\varphi(v\_2)=v\_{36}$, then $\varphi(v\_3)=v\_{35}$, and we have no possible value for $\varphi(v\_4)$. We get $\varphi(v\_2)=v\_2,\varphi(v\_3)=v\_3,\varphi(v\_4)=v\_4$. Next $\varphi(v\_5)\in\{v\_3,v\_5\}$, but for $\varphi(v\_5)=v\_3$ we get $\varphi(v\_6)=v\_4$, with no possible value for $\varphi(v\_7)$. So $\varphi$ must be the identity on the entire run $v\_1\to\ldots\to v\_7$, and by repeating the same argument for the remaining runs, the same is true on all of $D$. In particular, $\varphi$ does not map $D$ onto a proper subgraph.

> **Comments:**
> **username_4**: This same analysis shows that all balanced oriented cycles with two runs that are cores have length at least 24, right? So that gives a lower bound on the answer to the main problem.  
> **username_3**: Yes, good point.  
> **username_0**: Great, thanks, this is very helpful! Can we convince ourselves by hand that this is a core? (note that there is a polynomial-time algorithm to check if an oriented cycle $D$ is a core: create the set of $|V(D)|$ oriented sub-paths $\{D-a$ such that $a$ is an arc of $D\}$, and then check if $D$ maps to any of these paths; this can be done in polytime, see Gutjahr et al: http://www.sciencedirect.com/science/article/pii/0166218X9290294K)  
> **username_3**: @FlorentFoucaud I've added a bit showing that $D$ is a core.  

---

