3
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Farah Mind
    Dec 21, 2019 at 19:18
  • $\begingroup$ Yes, the weight of color doesn't depend on the vertex. $\endgroup$
    – Laakeri
    Dec 21, 2019 at 19:22
  • $\begingroup$ 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? $\endgroup$
    – Farah Mind
    Dec 21, 2019 at 19:44
  • $\begingroup$ Yes. If $P_2$ is NP-hard and can be polynomially reduced to $P_1$, then $P_1$ is also NP-hard. $\endgroup$
    – Laakeri
    Dec 21, 2019 at 19:50
  • $\begingroup$ and do you know about any results on the sum coloring of interval graphs when the time horizon of the interval graph is bounded. $\endgroup$
    – Farah Mind
    Jan 10, 2020 at 14:58
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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$? $\endgroup$
    – D.W. ♦
    Dec 25, 2019 at 17:21
  • $\begingroup$ 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. $\endgroup$
    – Narek Bojikian
    Dec 25, 2019 at 20:16

Your Answer

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

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