# Coloring an interval graph with weights

I have an interval graph $$G=(V,E)$$ and a set of colors $$C=\{c_1,c_2,...,c_m\}$$, when a color $$c_i$$ is assigned to a vertex $$v_j$$, we have a score $$u_{ij}\geq 0$$. The objective is to find a coloring of $$G$$ with at most $$m$$ colors that maximizes the total score (sum of the scores of the vertices).

Do you know about any results in the literature that may help me to find the complexity of this problem?

The sum coloring problem can be reduced to this problem by having $$n$$ possible colors with weights $$u_{ij} = n - i$$. Sum coloring is NP-hard for interval graphs.

• do you mean that the number of colors in this case is equal to the number of vertices and that each color has the same weight on all the vertices? Dec 21, 2019 at 19:18
• Yes, the weight of color doesn't depend on the vertex. Dec 21, 2019 at 19:22
• In my problem (say $P_1$), the weights depend on the vertices and on the colors. In you answer you mean that the problem with $u_{ij}=n-i$ (say $P_2$) is a subproblem of ($P_1$). Since the sum coloring can be reduced to ($P_2$), the $(P_2)$ is NP-hard and therefore $(P_1)$ is also NP-hard? Dec 21, 2019 at 19:44
• Yes. If $P_2$ is NP-hard and can be polynomially reduced to $P_1$, then $P_1$ is also NP-hard. Dec 21, 2019 at 19:50
• and do you know about any results on the sum coloring of interval graphs when the time horizon of the interval graph is bounded. Jan 10, 2020 at 14:58

It is quite common for greedy algorithms to turn into dynamic programming algorithms when adding weights to the problem. Here is a solution for a constant number of colors (a small value of $$m$$). Note that interval graph are perfect graphs (which we need to prove the correctness of the algorithm below).

Let $$v_1, \dots v_n$$ be an enumeration of the vertices of the graph according to an interval embedding. The dynamic programming states are the possible colorings of intervals of size $$m$$. Formally, Let $$C:V\times C^m\rightarrow \mathbb{N}$$ be the function that assigns to each interval starting at a vertex $$v_i$$ for $$i \leq n-m$$ and has length $$m$$, the minimum weight of a coloring of the subgraph induced by vertices $$v_j ; j \geq i$$. Formally: $$C(i, c_0, \dots, c_{m-1}) := \text{minimum weight coloring of } G[\{v_j ;j\geq i\}] \\ \text{; where v_{i + k} is colored c_k for k \in \{0,\dots m-1\}}$$

As an exercise you can build the transitions of the of the dynamic programming table and proof its correctness.

Note. @Laakeri refered a link to the hardness of the problem. Is implies that an algorithm parameterized by the chromatic number of the graph is a good approach (since we cannot hope for a polynomial time algorithm and this algorithm is even linear in the size of the graph an multiplied by an exponential factor of the chromatic number).

• Can you give a hint on why this is correct? I am not seeing how to handle edges between $v_{i+k}$ and $v_j$ (when $j\ge k+m$), or how to use the fact that it is a perfect graph. Why do you have ${C \choose 2}^m$ instead of $C^m$?
– D.W.
Dec 25, 2019 at 17:21
• Perfect graphs for that we can check whether the colorimg exists efficiently and we are left with the problem of optimizing costs (and that it suffices to look at the last k vrtices in the interval). In case a coloring exists, we won't have such edges (in intervalgraphs such edges imply huge clicks). Otherwise we need a bigger value of n anyway. I think it should be $C^m$ instead of ${C\choose 2}^m$ I will check it again later and update accordingly. Thanks for the notice. Dec 25, 2019 at 20:16