Colorir um gráfico de intervalo com pesos

Question

Eu tenho um gráfico de intervalo $ g= (v, e) $ e um conjunto de cores $ c=$ c= \{c_1, c_2, ..., c_m \} $ , quando uma cor $ c_i $ é atribuído a um vértice $ v_J $ , temos uma pontuação $ u_ {ij} \ Geq 0 $ .O objetivo é encontrar uma coloração de $ g $ com no máximo $ m $ cores que maximizam o totalpontuação (soma dos escores dos vértices).

Você sabe sobre qualquer resultado na literatura que pode me ajudar a encontrar a complexidade desse problema?

Answer 1

O problema de coloração de soma pode ser reduzido a este problema, tendo $ n $ possíveis cores com pesos $ u_ {ij}= n - i $ .Sum Coloring é NP-DURO para gráficos de intervalo.

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

.

Answer 2

É bastante comum que os algoritmos gananciosos se transformem em algoritmos de programação dinâmicos ao adicionar pesos ao problema. Aqui está uma solução para um número constante de cores (um pequeno valor de $ m $ ). Note que o gráfico de intervalo é perfeitas gráficos (que precisamos provar a exportação do algoritmo abaixo) .

Deixe $ v_1, \ Dots v_n $ ser uma enumeração dos vértices do gráfico de acordo com uma incorporação de intervalo. Os estados de programação dinâmica são as possíveis corantes de intervalos de tamanho $ m $ . Formalmente, deixe $ c: v \ vezes c ^ m \ rightarrow \ mathbb {n} $ seja a função que atribui a cada intervalo a partir de uma vértice $ v_i $ para $ i \ leq nm $ e tem comprimento $ m $ , o peso mínimo de uma coloração da subgraph induzida por vértices $ v_j; j \ geq i $ . Formalmente: $$ C (I, C_0, \ Dots, C_ {M-1}):=Texto {coloração mínima de peso de} g [\ \ {v_j; j \ geq i \} ] \\ \texto{; onde $ v_ {i + k} $ é colorido $ c_k $ por $ k \ in \ {0, \ DOTS m-1} $} $$

Como um exercício, você pode construir as transições da tabela de programação dinâmica e prova sua exatidão.

Nota. @laakeri referiu um link para a dureza do problema. É implica que um algoritmo parametrizado pelo número cromático do gráfico é uma boa abordagem (já que não podemos esperar por um algoritmo de tempo polinomial e este algoritmo é mesmo linear no tamanho do gráfico um multiplicado por um fator exponencial) .