Colorare un grafico a intervalli con pesi

Question

Ho un grafico a intervalli $ g= (v, e) $ e un set di colori $ c= \{c_1, c_2, ..., c_m \} $ , quando un colore $ c_i $ è assegnato a un vertice $ V_J $ , abbiamo un punteggio $ u_ {ij} \ geq 0 $ .L'obiettivo è trovare una colorazione di $ G $ con al massimo $ m $ colori che massimizzano il totalePunteggio (somma dei punteggi dei vertici).

Sai di qualsiasi risultato in letteratura che potrebbe aiutarmi a trovare la complessità di questo problema?

Answer 1

Il problema di colorazione della somma può essere ridotto a questo problema con $ N $ possibili colori con pesi $ u_ {ij}= n - I $ .La colorazione della somma è NP-HARD per grafici a intervalli.

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

.

Answer 2

È abbastanza comune per gli algoritmi avidi trasformarsi in algoritmi di programmazione dinamici quando si aggiungono pesi al problema. Ecco una soluzione per un numero costante di colori (un piccolo valore di $ m $ ). Nota che l'intervallo grafico è grafici perfetti (che dobbiamo dimostrare la correttezza dell'algoritmo sottostante) .

Let $ V_1, \ Dots v_n $ Sii un'enumerazione dei vertici del grafico in base a un intervallo di incorporamento. Gli stati di programmazione dinamica sono le possibili colorazioni di intervalli di dimensioni $ m $ . Formalmente, let $ c: v \ volte c ^ m \ reapyarrow \ mathbb {n} $ essere la funzione che assegna a ciascun intervallo a partire da un vertice $ V_i $ per $ i \ Leq Nm $ e ha lunghezza $ m $ , il peso minimo di una colorazione del sottografo indotto dai vertici $ v_j; j \ geq I $ . Formalmente: $$ c (i, c_0, \ dots, c_ {m-1}):=testo {Colorazione minima di peso minimo di} g [\ {v_j; j \ geq i \} ] \\ \testo{; dove $ v_ {i + k} $ è colorato $ c_k $ per $ k \ in \ {0, \ dots m-1 \} $} $$

Come esercizio è possibile costruire le transizioni della tabella di programmazione dinamica e prova la sua correttezza.

Nota. @Laakeri ha riferito un collegamento alla durezza del problema. È implica che un algoritmo parametrizzato dal numero cromatico del grafico è un buon approccio (dal momento che non possiamo sperare in un algoritmo di tempo polinomiale e questo algoritmo è persino lineare nella dimensione del grafico un moltiplicato da un fattore esponenziale del numero cromatico) .