I have weighted graph for sensor networks with aggregation nodes and sensors. There is a edge between two nodes associated with a weight. Higher the weight, stronger the interference between the aggregation nodes if they have same color.

I need to perform graph coloring of these nodes with just K colors. The nodes with higher edge weight should/must have different colors.

What is an efficient way to do the optimal coloring?


May be the coloring of such a big network is too difficult. Instead we can have clusters of nodes and then do the intra-cluster coloring. But then we need to take care of inter-cluster interference.


1 Answer 1


I recommend first trying to solve the problem directly. For each edge $(i,j)$, let $c_{ij}$ be the edge weight. Let binary decision variable $x_{ik}$ indicate whether node $i$ is assigned color $k$. The problem is to minimize $$\sum_{i,j} c_{ij} \sum_k x_{ik} x_{jk}$$ subject to $\sum_k x_{ik} = 1$ for all $i$. You can call an MIQP solver or linearize the quadratic objective. To linearize, for each edge $(i,j)$ with $c_{ij}>0$, introduce binary (or just nonnegative) decision variable $y_{ij}$ to represent $\sum_k x_{ik} x_{jk}$, impose additional constraints $y_{ij} \ge x_{ik} + x_{jk} - 1$, and minimize $\sum_{i,j} c_{ij} y_{ij}$.

  • $\begingroup$ you can see that there are large number of nodes. As it is clear from the problem description that one node will more more likely 5 to 6 nodes, i.e., most of $c_{i,j}$ are zero. How to take this into consideration o make the problem smaller/simpler? $\endgroup$
    – KGM
    Commented Apr 13, 2023 at 13:49
  • $\begingroup$ I would not be surprised if this problem can be solved quickly for a sparse graph with 500 nodes. You do not need $y_{ij}$ or its constraint if $c_{ij}=0$. I'll update my answer. $\endgroup$
    – RobPratt
    Commented Apr 13, 2023 at 13:54
  • $\begingroup$ This is the same model I suggested here: or.stackexchange.com/a/10238/500 $\endgroup$
    – RobPratt
    Commented Apr 13, 2023 at 14:43
  • $\begingroup$ the second constraint can be expressed as: for $c=1:C$, for $i=1:N-1$, for $j=i+1:N$, if $w_{ij}>0$ $y_{ij}\ge x_{ic}+x_{jc}-1$, end if, end for, end for, end for. Am I right? $\endgroup$
    – KGM
    Commented Apr 26, 2023 at 10:51
  • 1
    $\begingroup$ Yes, this model allows such improper colorings. For edge $(i,j)$, if nodes $i$ and $j$ are assigned the same color $k$, then $x_{ik}=x_{jk}=1$, the constraints enforce $y_{ij}=1$, and the weight $c_{ij}$ is accrued. $\endgroup$
    – RobPratt
    Commented May 11, 2023 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.