重みを持つ間隔グラフを着色する

Question

I間隔グラフ $ g=（v、e）$ と一連の色 $ c= \{C_1、C_2、...、C_M \} $ 、color $ c_i $ が頂点 $ v_j $ 、私たちはスコア $ u_ {ij} \ geq 0 $ です。目的は、 $ g $ の着色を見つけることです。スコア（頂点のスコアの合計）

この問題の複雑さを見つけるのを助けることができる文学の結果について知っていますか？

Answer 1

$ n $ $ n $ $ u_ {ijを持つことで、この問題に和らげることができます。}= n - i $ 。合計着色は間隔グラフにNPハードです。

ソース： https://en.wikipedia.org/wiki/sum_coloring

Answer 2

問題に重みを加えるときに、貪欲なアルゴリズムが動的プログラミングアルゴリズムに変えることは非常に一般的です。これは、一定数の色（ $ m $ の小さい値）の解決策です。間隔グラフは完璧なグラフ（以下のアルゴリズムの正当性を証明する必要があります） 。

$ v_1、\ dots v_n $ は、インターバルの埋め込みに従ってグラフの頂点の列挙です。動的プログラミング状態は、サイズ $ m $ の間隔の可能な配色です。正式には、 $ c：v vide} $ {n} $ vertex $ v_i $ for $ i \ leq nm $ 、長さ $ m $ 、vertices $ v_jによって誘起されたサブグラフの色付けの最小重量。 j \ geq i $ 。正式に： $$ c（i、c_0、\ dots、c_ {m-1}）：=text {} g [\ {v_j; j \ geq i \} ] \\ \ text {;ここで、$ v_ {i + k} $は$ k \ in \ in \ {0、\ dots m-1 \} $ $} $ c_k $の色付き$ c_k $} $$

運動として、動的プログラミングテーブルの遷移を構築し、その正当性を証明することができます。

注意事項 @Laakeriは問題の硬さへのリンクを参照しました。グラフの色番号によってパラメータ化されたアルゴリズムが良いアプローチであることを意味します（多項式の時間アルゴリズムを希望することはできず、このアルゴリズムはグラフのサイズでさえ線形数の指数関数の要因を乗じたもの） 。