Karp hardness of digraph coloring without monochromatic dicycle

Question

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?

Answer 1

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.

Answer 2

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.