NP-Completeness of a Graph Coloring Problem

Problem Detail: 

Alternative Formulation

I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to describe the problem. However, I believe that the alternative formulation is still NP-hard. The alternative formulation uses a disjoint set of incoming and outgoing nodes that simplifies the problem definition.

Given $n$ outgoing and $n$ incoming nodes (the red and blue nodes in the figure respectively), and a set $w_{ij}$'s of size $n \times n$ of edge weights between the outgoing and incoming vertices. The goal of the problem is to color the thick edges in the figure so that for every incoming node, a condition holds.

Given a set $\{ O_i \; | \; i=1 \dots n \}$ of output vertices, a set $\{ I_i\; | \; i=1 \dots n \}$ of input vertices, $n \times n$ weights $w_{ij} \ge 0$ between $O_i$'s and $I_j$'s for $i,j=1 \dots n$, and a positive constant $\beta$, find the minimum number of colors for the edges $e_{ii}$ (thick edges in the above figure) such that for all $j=1 \dots n$,

$$ \frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta $$

where $c(i)$ shows the color of the edge $e_{ii}$.

---

Old Formulation

The following problem looks NP-hard to me, but I couldn't show it. Any proof/comment to show the hardness or easiness of it is appreciated.

Assume $K_n=\langle V,E \rangle$ is a complete weighted directed graph with $n$ nodes and $n(n-1)$ edges. Let $w_{ij} \ge 0$ show the weight of the edge $ij$ and $c(ij)$ shows the color of edge $ij$. Given a subset of the edges $T \subseteq E$ and a positive constant $\beta$ the goal is: find the minimum number of colors such that for each $e_{ij} \in T$:

$$ \frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta. $$ and $$ c(ij) \neq c(ik) \quad for \quad j \neq k $$

Please note that in the above problem, only the edges in $T$ needs to be colored. That is the problem can be solved in $\mathcal{O}(|T|!)$.

Update:

After Tsuyoshi Ito's comment I updated the problem. The denominator is changed from $1+\sum_{c(kj)=c(ij),k \neq i,e_{kj} \in T} w_{kj}$ to $1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}$. Therefore, the denominator contains the weights outside $T$ as well. That's actually why I mentioned the complete graph in the definition.

I also added an additional constraint $c(ij) \neq c(ik) \quad for \quad j \neq k$. That means, the outgoing edges from a node must be of different colors (but the incoming colors can be the same as long as the inequality holds). This puts an intuitive lower bound on the number of colors, which is the maximum out-degree of the nodes in $T$.

As Tsuyoshi mentioned, $w_{ij}$'s, $T$, and $\beta$ are inputs to the problem and the edge colors are the output.

Update 2:

Problem does not enforce the edges $e_{ij}$ and $e_{ji}$ be of a same color.

Asked By : Helium

Answered By : Helium

It is quite simple to show that the alternative formulation is NP-hard. The reduction is from the vertex coloring problem. Given a graph G with $n$ vertices, we create an instance of the above problem with $n$ output vertices and $n$ input vertices. Weights are set as follows: For all $i$, let $w_{ii}=1$. For $i \neq j$, if there is an edge between vertex $i$ and vertex $j$, let $w_{ij}=w_{ji}=1$, else let $w_{ij}=w_{ji}=0$. In addition, let $\beta=1$.

This is quite obvious but difficult to describe why the reduction is correct. Let $\mathcal{C}$ show the instance of the graph coloring and $\mathcal{R}$ show the reduced instance of the problem. To show the above reduction gives a correct solution we need to show that (1) every valid coloring for $\mathcal{R}$ is valid for $\mathcal{C}$ as well. (2) the answer given by $\mathcal{R}$ is minimal for $\mathcal{C}$.

If $i$ and $j$ are two adjacent vertices of $\mathcal{C}$, then they must have different colors in $\mathcal{R}$. That is because if $i$ and $j$ are adjacent and they have the same color, the fraction $\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$ would result in $\frac{1}{1+X}$, where $X$ has a positive value. Therefore, the condition does not hold. In addition, every valid (but not necessarily minimal) coloring for $\mathcal{C}$, is a valid coloring for $\mathcal{R}$ as well. It follows the fact that in a valid coloring of $\mathcal{C}$, every pair of adjacent nodes have different colors, so the condition holds for all the colored edges of $\mathcal{R}$ in the solution. Since every coloring of $\mathcal{C}$ is a valid coloring for $\mathcal{R}$, the minimal solution to $\mathcal{R}$ must be a minimal solution to $\mathcal{C}$ as well. Otherwise, it is not a minimal one because the solution to $\mathcal{C}$ gives a solution with a smaller number of colors.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2157