patternMinor
NP-Completeness of a Graph Coloring Problem
Viewed 0 times
completenessproblemcoloringgraph
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
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
Solution
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.
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.
Context
StackExchange Computer Science Q#2157, answer score: 3
Revisions (0)
No revisions yet.