9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Feb 19 '16 at 0:31
  • $\begingroup$ 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... $\endgroup$ – Florent Foucaud Feb 19 '16 at 12:24
  • $\begingroup$ You are right, the construction I proposed is too simple. $\endgroup$ – András Salamon Feb 19 '16 at 15:16
  • $\begingroup$ 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). $\endgroup$ – Florent Foucaud Feb 19 '16 at 17:36
  • $\begingroup$ 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. $\endgroup$ – András Salamon Feb 19 '16 at 18:05
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – David Eppstein Feb 25 '16 at 21:42
  • $\begingroup$ Yes, good point. $\endgroup$ – Klaus Draeger Feb 26 '16 at 0:40
  • 1
    $\begingroup$ 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: sciencedirect.com/science/article/pii/0166218X9290294K) $\endgroup$ – Florent Foucaud Feb 26 '16 at 18:01
  • 1
    $\begingroup$ @FlorentFoucaud I've added a bit showing that $D$ is a core. $\endgroup$ – Klaus Draeger Feb 27 '16 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.