Colorear un gráfico de intervalo con pesas.

Question

Tengo un gráfico de intervalo $ g= (v, e) $ y un conjunto de colores $ c= \{C_1, C_2, ..., C_M \} $ , cuando un color $ c_i $ se asigna a un vértice $ v_j $ , tenemos un puntaje $ u_ {ij} \ geq 0 $ .El objetivo es encontrar una coloración de $ g $ con el más $ m $ colores que maximizan el totalPuntuación (suma de las puntuaciones de los vértices).

¿Conoce los resultados en la literatura que pueda ayudarme a encontrar la complejidad de este problema?

Answer 1

El problema de coloración de la suma se puede reducir a este problema al tener $ n $ Posibles colores con pesas $ u_ {ij}= n - i $ .La coloración de suma es NP-HARD para los gráficos de intervalo.

Fuente: https://en.wikipedia.org/wiki/sum_coloring

Answer 2

Es bastante común que los algoritmos codiciosos se conviertan en algoritmos de programación dinámicos al agregar pesas al problema. Aquí hay una solución para un número constante de colores (un pequeño valor de $ m $ ). Tenga en cuenta que el gráfico de intervalo es gráficos perfectos (que necesitamos para demostrar la corrección del algoritmo a continuación) .

Let $ v_1, \ dots v_n $ será una enumeración de los vértices del gráfico de acuerdo con un intercambio de intervalo. Los estados de programación dinámica son los posibles colorantes de los intervalos de tamaño $ m $ . Formalmente, deja que $ C: V \ Times C ^ M \ RightArow \ MathBB {n} $ Sé la función que asigna a cada intervalo que comienza en un vértice $ V_I $ para $ i \ leq nm $ y tiene longitud $ m $ , el peso mínimo de un colorante del subgrafo inducido por vértices $ v_j; j \ geq i $ . Formalmente: $$ C (I, C_0, \ PUNTOS, C_ {M-1}):=Text {colorante de peso mínimo de} G [\ {V_J; J \ GEQ I \} ] \\ \texto{; donde $ v_ {i + k} $ es coloreado $ c_c_ $ por $ k \ in \ {0, \ dots m-1 \} $} $$

Como ejercicio, puede construir las transiciones de la tabla de programación dinámica y pruebe su corrección.

nota. @lakeri refirió un enlace a la dureza del problema. Es implica que un algoritmo parametrizado por el número cromático del gráfico es un buen enfoque (ya que no podemos esperar un algoritmo de tiempo polinomial y este algoritmo sea incluso lineal en el tamaño del gráfico y se multiplica por un factor exponencial del número cromático) .