NP-Completeness of a Graph Coloring Problem

Question

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.

Answer 1

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.

Answer 2

EDIT: The construction below doesn't quite work, as per Tsuyoshi Ito's comment below, it doesn't enforce that $c(ij)=c(ji)$. I leave it up in case it's a useful start though. Also, $T$ shouldn't include arcs with weight $0$.

Along the lines Mohsen suggested, start with Edge Coloring, convert the graph $G=(V,E)$ to a digraph $D=(V,A)$ on the same vertex set where $\forall uv\in E$ we have $(u,v)$ and $(v,u)$ in $A$, give all arcs $a \in A$ (at this point) weight $w_{a} = 1$, then $\forall xy \notin E$ add $(x,y)$ and $(y,x)$ to $A$ with $w_{xy}=w_{yx}=0$, set $\beta$ to $1$ and $T=A$.

Then the condition is only satisfied if no two arcs incident on the same vertex have the same colour, disregarding arcs that come from non-edges in the original graph (as they have weight $0$). This colouring can then be converted back to a proper colouring for the original graph.

Technically I've converted your original problem to a decision problem ("is the graph colourable with $k$ colours?"), but this needed to be done to fit into $NP$ anyway and it's effectively interchangable up to a polynomial.

So I think that works, or have I just shown something else to be $NP$-hard? ;)