6
$\begingroup$

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.

A $\theta$-improper coloring of $G$ is a coloring where each node can have at most $\theta$ neighbors with the same coloring.

Now, given a weighted digraph $G(V,A,\omega)$ with weight function $\omega(u,v), (u,v)\in A$, a weighted $\theta$-improper $k$-coloring of $G$ is a coloring of the nodes such that for every node $v$:

$$ \sum_{u \in N(v)|c(u)=c(v)}\omega(u,v)\le \theta, $$

where $N(v)$ denotes the adjacent vertices of $v$, and $c(v)$ denotes the color of vertex $v$. Note that this definition generalizes $\theta$-improprer colorings (chose weights equal to 1), and standard colorings (…and chose $\theta=0)$. Let this problem be $P_2$.

It is fairly easy to prove that finding a weighted $\theta$-improper coloring is an $\mathcal{NP}$ complete problem by proving that $P_1\propto P_2$ (by choosing an appropriate weight function), but I am struggling to prove that $P_2 \propto P_1$ (this is necessarily true, since both problems are $\mathcal{NP}$ complete.

In other words, given a weighted digraph $G(V,A,\omega)$, how can one find a weighted $\theta$-improper $k$-coloring of $G$ with a procedure that solves the standard $k$-coloring problem?

$\endgroup$
2
  • $\begingroup$ What about converting to SAT and then to coloring? $\endgroup$
    – joro
    Sep 27, 2015 at 4:51
  • $\begingroup$ Presumably N(v) should be the adjacent vertices that have the same colour, or am I missing something? Is there any reason to expect that the more general problem reduces to the original one? In general, you wouldn't expect there to be a "natural" direct reduction between two arbitrary different NP-complete problems (i.e., one which preserves some combinatorial feature of the instances, rather one that e.g. goes via SAT or some other unrelated NP-complete problem). $\endgroup$ Sep 27, 2015 at 11:21

2 Answers 2

3
$\begingroup$

It's interesting to notice that weighted improper $k$-coloring seems $NP$-complete even for $\theta = 1, k = 2$; so unless $P=NP$ there is not a polynomial time reduction to $k$-coloring ($k = 2$); because $2$-coloring of graphs is in $P$.

A sketch of the reduction from NAE 3-SAT to unweighted $\theta=1$ improper 2-coloring of undirected graphs is the following [NOTE: I quickly made it for exercise, so it can be wrong or probably the result is already known].

  • represent each variable $x_i$ with two $K_4$ gadgets, one node of the first $K_4$ represents $+x_i$, one node of the second $K_4$ represents $-x_i$; the nodes $+x_i$ and $-x_i$ are linked together and they cannot have the same color;
  • represent each clause $Cj = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$ with a $K_3$ gadget; the three nodes $\ell_{j,1}, \ell_{j,2}, \ell_{j,3}$ of a clause gadget cannot have the same color;
  • if $\ell_{j,p} = x_i$ then add an edge between $\ell_{j,p}$ and $+x_i$; if $\ell_{j,p} = \neg x_i$ then add an edge between $\ell_{j,p}$ and $-x_i$.

enter image description here

It's not hard to prove that the resulting graph is 1-improper 2-colorable if and only if it exists an assignment of the $x_i$s such that in each $C_j$ at least one literal is true and at least one literal is false (Not-All-Equal).

The NP-completeness of weighted $\theta = 1$ improper 2-coloring of directed graphs follows from:

  1. weighted $\theta = 1$ improper 2-coloring of directed graphs is simply a generalization of unweighted $\theta = 1$ improper 2-coloring of directed graphs (build an NPC reduction setting weight = 1);
  2. $\theta = 1$ improper 2-coloring of directed graphs $\theta = 1$ improper 2-coloring of directed graphs is simply a generalization $\theta = 1$ improper 2-coloring of undirected graphs $\theta = 1$ (build an NPC reduction setting $w(u,v) = w(v,u)$)
$\endgroup$
0
$\begingroup$

Don't know how the simplest "manual" reduction would look like.

One possible approach is convert improper coloring to SAT (say with a tool like CBMC) and then convert SAT to coloring.

This is polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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