How can I prove that these two graph coloring problems are polynomial time equivalent?

Question

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?

Answer 1

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

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)$)

Answer 2

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.