Problema della colorazione dei vertici (VCP)¶
Definizione 1: Problema della colorazione dei vertici
Dato:
-
un grafo semplice \(G = (V,E)\), dove
\[ V = \{1,2,\dots,n\} \]è l'insieme degli \(n\) vertici e
\[ E \subseteq \big\{\, \{u,v\} : u,v \in V,~ u \neq v \,\big\} \]è l'insieme degli \(m\) lati,
il problema della colorazione dei vertici (VCP) chiede di decidere come assegnare un colore a ogni vertice, in modo che due vertici adiacenti non abbiano lo stesso colore e il numero totale di colori usati sia minimo.
Ipotesi
-
Facciamo le seguenti ipotesi:
-
Il grafo non ha vertici isolati. Un vertice isolato può ricevere un qualunque colore usato dal resto del grafo; se il grafo non ha lati, il valore ottimo è uno. Formalmente:
\[ \deg(v) \ge 1, \qquad \forall\, v \in V. \] -
Nessun vertice ha l'intorno contenuto nell'intorno di un altro vertice. Formalmente:
\[ N(u) \not\subseteq N(v), \qquad \forall\, u,v \in V,~ u \neq v. \]
-
-
La seconda ipotesi si può fare senza perdita di generalità, perché:
-
se \(N(u) \subseteq N(v)\), il vertice \(u\) si può eliminare senza cambiare il numero cromatico: ogni colorazione di \(G \setminus \{u\}\) si estende a \(u\) con il colore di \(v\);
-
i vertici \(u\) e \(v\) non sono adiacenti: altrimenti \(v \in N(u) \subseteq N(v)\), il che è impossibile in un grafo semplice, quindi \(u\) e \(v\) possono condividere un colore.
-
Che cosa fa il corso su questo problema¶
| Tecnica | Dove |
|---|---|
| Definizione | Cap. 4 «Problemi di colorazione» |
| Formulazioni | Cap. 11 «Formulazioni dei problemi di colorazione» |
| Euristiche | Cap. 30 «Euristiche costruttive» |
| Limiti dell'approssimazione | Cap. 37 «Colorazione dei vertici: limiti dell'approssimazione» |
| Algoritmi ad hoc | Cap. 42 «Colorazione dei vertici: il branch-and-bound DSATUR» |
| Esercizi | Cap. 4 (5 esercizi); Cap. 11 (5 esercizi); Cap. 30 (3 esercizi); Cap. 37 (5 esercizi); Cap. 42 (5 esercizi) |
Proprietà¶
-
NP-difficile in senso forte: decidere se \(\chi(G)\le 3\) è NP-completo (Cap. 1).
-
Bound di cricca \(\omega(G) \le \chi(G)\) e bound degli insiemi stabili \(\lceil n/\alpha(G) \rceil \le \chi(G)\) (Cap. 4).
-
I bound possono non raggiungere \(\chi(G)\): sul grafo di Petersen \(\omega(G)=2<\chi(G)=3\) (Cap. 4).
-
Brooks: \(\chi(G)\le\Delta\) per un grafo connesso che non è né completo né un ciclo dispari (Cap. 4).
Formulazioni¶
-
Il modello \(\ILP_{\VCP}\) ha \(kn\) variabili \(x_{vc}\) e \(k\) variabili \(y_c\), e \(k!\) copie equivalenti di ogni colorazione (Cap. 11).
-
Entrambi i rilassamenti lineari valgono \(2\) per ogni grafo con almeno un lato (Cap. 11).
-
Sul grafo completo con \(n\) vertici il gap è \(n-2\) e il rapporto \(\frac{2}{n}\) tende a \(0\) (Cap. 11).
Euristiche¶
-
La colorazione greedy usa al più \(\Delta(G)+1\) colori, e l'ordine dei vertici conta (Cap. 30).
-
\(DSATUR\) colora per primo il vertice che vede più colori; è esatto sui grafi bipartiti (Cap. 30).
Approssimazione¶
-
Non approssimabile: nessun algoritmo polinomiale garantisce un rapporto inferiore a \(\frac43\), a meno che \(P=NP\), e nemmeno \(n^{1-\varepsilon}\) (Zuckerman) (Cap. 37).
-
Casi particolari: grafi bipartiti e grafi di intervalli in modo esatto, grafi planari entro \(2\) colori dall'ottimo (Cap. 37).