# Karp hardness of digraph coloring without monochromatic dicycle

Problem statement:

Input: a digraph $$G(V, A)$$ and a natural number $$k$$

Output: YES if it is possible to color all vertices of $$V(G)$$ by $$k$$ colors such that no directed cycle is monochromatic, NO otherwise

Is this an $$NP$$-complete problem?

• $k$-coloring is a coloring without any arc having head and tail colored by the same color. But, our notion in this problem is a coloring of a digraph without monochromatic dicycles. Sep 28 '18 at 15:00

Yes, it is NP-complete. There appears to be a straightforward reduction from graph coloring. If $$G_u$$ is an undirected graph, define the directed graph $$G_d$$ by replacing each undirected edge $$(v,w)$$ in $$G_u$$ with two directed edges $$(v,w)$$ and $$(w,v)$$. Then $$G_u$$ can be colored with $$k$$ colors iff $$G_d$$ can be colored so that there is no monochromatic directed cycle.

• Nope, this would make each color an independent set while in our problem, it is not necessarily like so. Sep 29 '18 at 7:41
• @ThinhD.Nguyen, I think you might have prematurely rejected this answer (or else I have not understood your comment). Can you give a concrete example of where you think the reduction fails? (Note: it suffices to prove that a special case of your problem is NP-hard. There is a special case of your problem where the colors form an independent set. I believe my answer proves that this special case is NP-hard. It follows that your general problem is also NP-hard... even if there are instances of your general problem where each color doesn't form an independent set.)
– D.W.
Sep 29 '18 at 17:24
• Ok, you are right. This is much easier. Sep 29 '18 at 20:33
• Actually, if we change from digraph to oriented graph (for each pair of $u$, $v$, only $3$ possible cases: $(u,v)$ is present, $(v,u)$ is present, or none), then your simple reduction does not work. That is why my reduction is so lengthy. Sep 30 '18 at 10:38

Our problem is $$\mathrm{NP}$$-complete by a Karp reduction from $$\mathrm{NAE}$$-$$\mathrm{3SAT}$$

In fact, both the undirected and directed version are $$\mathrm{NP}$$-complete. First, we will describe the reduction for the undirected version. Then, we show how to orient all the edges of the undirected graph to obtain a digraph to finish the reduction for the directed version.

REDUCTION FOR UNDIRECTED VERSION

Given an instance of $$\mathrm{NAE}$$-$$\mathrm{3SAT}$$, we will construct an undirected graph such that there exists a solution for the $$\mathrm{NAE}$$-$$\mathrm{3SAT}$$ instance if and only if it is possible to color the vertices of this graph by $$2$$ colors such that no cycle is monochromatic.

For each clause $$j$$, create a $$K_3$$ cycle each vertex of which corresponds to one literal of clause $$j$$.

Now, for each pair of opposite literals (one positive and one negative literal of the same variable) $$l_{jm}=x_i$$ and $$l_{kn}=\lnot x_i$$, we connect them by a gadget as follows. (Here, $$l_{ab}$$ is literal $$b$$th of clause $$a$$, where $$1\leq b\leq 3$$)

The gadget to connect $$l_{jm}$$ and $$l_{kn}$$ is described now:

• Connect $$l_{jm}$$ and $$l_{kn}$$ by an edge
• Create $$3$$ new vertices $$a$$, $$b$$, $$c$$ (each gadget has its own three vertices like these)
• Connect these $$3$$ vertices $$a$$, $$b$$, $$c$$ to form a $$K_3$$ cycle
• Connect each of $$a$$, $$b$$, $$c$$ with both $$l_{jm}$$ and $$l_{kn}$$

Call the obtained undirected graph $$G$$. Set $$k=2$$. The reduction returns the instance $$(G,k)$$ of our problem.

Now, we prove the correctness of our reduction (for the undirected version).

If the given $$\mathrm{NAE}$$-$$\mathrm{3SAT}$$ is satiafiable, then given a solution, one can color all the $$\mathrm{TRUE}$$ literal-vertices $$\mathrm{RED}$$ and all the $$\mathrm{FALSE}$$ literal-vertices $$\mathrm{GREEN}$$. For each gadget described above, we color $$a$$ and $$b$$ by $$\mathrm{RED}$$ and $$c$$ by $$\mathrm{GREEN}$$. Next, we show that this is a solution to the produced instance of our problem.

Clearly, we use only $$k=2$$ colors as required. For each $$K_3$$ corresponding to one of the clauses, its $$3$$ vertices cannot be colored by the same color, because a solution to an $$\mathrm{NAE}$$-$$\mathrm{3SAT}$$ instance would make every clause containing both $$\mathrm{TRUE}$$ literal (colored $$\mathrm{RED}$$) and $$\mathrm{FALSE}$$ literal (colored $$\mathrm{GREEN}$$).

For each gadget of $$2$$ opposite literals $$l_{jm}$$ and $$l_{kn}$$, we have that these $$2$$ are colored by different colors. So, every cycle (contained in this gadget) that contains both these two vertices is already non-monochromatic. Only one other cycle (contained in this gadget) is the $$K_3$$ of $$a$$, $$b$$ and $$c$$. But as mentioned above, $$a$$ is colored $$\mathrm{RED}$$ and $$c$$ is colored $$\mathrm{GREEN}$$. All other possible cycles in $$G$$ need to cross from a $$K_3$$ clause to other $$K_3$$ clause by passing through a gadget. But, to pass through a gadget of, say $$l_{jm}$$ and $$l_{kn}$$ (colored by different colors), such a cycle has to be non-monochromatic.

Conversely, if we can color $$G$$'s vertices by $$2$$ colors without making any cycle monochromatic, then we will now show that the given $$\mathrm{NAE}$$-$$\mathrm{3SAT}$$ instance is satiafiable.

For each literal-vertex $$l_{jm}=x_i$$, if $$l_{jm}$$ is colored $$\mathrm{RED}$$, we assign $$x_i$$ to $$\mathrm{TRUE}$$, otherwise assign it to $$\mathrm{FALSE}$$.

For each literal-vertex $$l_{jm}=\lnot x_i$$, if $$l_{jm}$$ is colored $$\mathrm{RED}$$, we assign $$x_i$$ to $$\mathrm{FALSE}$$, otherwise assign it to $$\mathrm{TRUE}$$.

Since each clause is a $$K_3$$ cycle, it has to contain both $$\mathrm{RED}$$ literal-vertex (assigned to $$\mathrm{TRUE}$$) and $$\mathrm{GREEN}$$ literal-vertex (assigned to $$\mathrm{FALSE}$$).

It is left to prove the consistency of the above mentioned assignment. This is guaranteed by the gadgets. Suppose to the contrary that there exist two oppisite literals $$l_{jm}$$ and $$l_{kn}$$ colored by the same color, that w.l.o.g. we can assume to be $$\mathrm{RED}$$. Then it is impossible to properly color $$a$$, $$b$$ and $$c$$. Indeed, since $$a$$, $$l_{jm}$$ and $$l_{kn}$$ form a cycle, we deduce that $$a$$ must be colored $$\mathrm{GREEN}$$. Similarly, $$b$$ and $$c$$ are also colored $$\mathrm{GREEN}$$. But, now the cycle $$(a,b,c)$$ is monochromatic. Thus, the above assignment is consistent. And we obtain a solution to the given $$\mathrm{NAE}$$-$$\mathrm{3SAT}$$.

REDUCTION FOR DIRECTED VERSION

We use exactly the same above reduction. Now, we have to orient all the edges of $$G$$ to obtain a digraph. For each, $$K_3$$ clause cycle, we are free to choose one of two ways to turn it into a directed cycle (dicycle). For each gadget of two opposite literals $$l_{jm}$$ and $$l_{kn}$$, we can orient to have an arc $$(l_{jm},l_{kn})$$ (the other way can be finished similarly). Now, we orient to make $$3$$ cycles: $$(l_{jm},l_{kn},a)$$, $$(l_{jm},l_{kn},b)$$, $$(l_{jm},l_{kn},c)$$. Then, we make one more cycle, namely $$(a,b,c)$$. By orienting like this, we can use all the above arguments for the undirected version. Note that the possible dicycles that cross from clause to clause still have to be non-monochromatic.