Coloring an interval graph with weights

Question

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?

Answer 1

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.

Source: https://en.wikipedia.org/wiki/Sum_coloring

Answer 2

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).