1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – Thinh D. Nguyen Sep 28 '18 at 15:00
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nope, this would make each color an independent set while in our problem, it is not necessarily like so. $\endgroup$ – Thinh D. Nguyen Sep 29 '18 at 7:41
  • $\begingroup$ @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.) $\endgroup$ – D.W. Sep 29 '18 at 17:24
  • $\begingroup$ Ok, you are right. This is much easier. $\endgroup$ – Thinh D. Nguyen Sep 29 '18 at 20:33
  • $\begingroup$ 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. $\endgroup$ – Thinh D. Nguyen Sep 30 '18 at 10:38
1
$\begingroup$

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.

$\endgroup$

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.