# NP-Completeness of a Graph Coloring Problem

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.

• @Raphael: Normally, an edge coloring problem looks to be a good candidate for the reduction. Finding the simplest np-hard problem for the reduction is the toughest part. The next step is to find the proper weights for the mapping. I guess, if an edge coloring problem is reduced to the above problem, the weights should be either like 0/1 or we need to solve a system of inequalities to find the weights. – Helium May 29 '12 at 10:00
• A few comments on the formulation of the problem: (1) What is the input? I guess that the input is w_ij for all edges, T, and β, but if so, you should not define w_ij and c(ij) as if they were given in the same way. (2) As I understand what you wrote, the edges outside T are never referred to. So it is simpler to define the directed graph consisting of the edges in T instead of considering to the complete directed graph. – Tsuyoshi Ito May 29 '12 at 10:52
• @TsuyoshiIto: Thanks for your comments, I updated the question. – Helium May 29 '12 at 22:42
• By the way, the problem looks quite messy to me. If you explain how you reached this problem (in other words, why you are interested in this problem), it might help others understand the problem. – Tsuyoshi Ito May 29 '12 at 23:28
• @TsuyoshiIto: 1) The problem is an special case of scheduling in wireless ad-hoc networks. $T$ refers to the transmission set and weights represent the signal attenuation coefficients. The fist constraint also refers to signal to interference plus noise ratio. 2) “the denominator only contains the weights of the edges in T” is deleted now. – Helium May 30 '12 at 0:06

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.

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? ;)

• How do you enforce that c(ij)=c(ji)? This is not necessarily true in the problem in question, if I understand it correctly. – Tsuyoshi Ito May 29 '12 at 12:36
• Good point. I'll edit the original post to note the problem. – Luke Mathieson May 29 '12 at 13:01