Problema della cricca massima (MCP)¶
Definizione 1: Problema della cricca massima
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 clique massima (MCP) chiede di trovare una clique \(K \subseteq V\) di \(G\) il cui numero di vertici sia massimo. Il suo valore ottimo è il numero di clique \(\omega(G)\).
Ipotesi
-
Consideriamo istanze non banali: il grafo ha almeno un lato e almeno un non-lato. Formalmente:
\[ 1 \le m < \binom{n}{2}. \] -
L'ipotesi si può fare senza perdita di generalità: se il grafo non ha lati, ogni singolo vertice è una clique massima e \(\omega(G)=1\); se il grafo è completo, \(V\) stesso è una clique e \(\omega(G)=n\).
Che cosa fa il corso su questo problema¶
| Tecnica | Dove |
|---|---|
| Definizione | Cap. 5 «Problemi di clique» |
| Formulazioni | Cap. 12 «Formulazioni dei problemi di clique» |
| Limiti dell'approssimazione | Cap. 38 «Clique massima: limiti dell'approssimazione» |
| Esercizi | Cap. 4 (2 esercizi); Cap. 5 (5 esercizi); Cap. 12 (5 esercizi); Cap. 38 (4 esercizi) |
Proprietà¶
-
NP-difficile: decidere se esiste una cricca con \(k\) vertici è uno dei \(21\) problemi NP-completi di Karp (Cap. 5).
-
Upper bound: grado \(\Delta+1\), lati, conteggio dei gradi \(k^{\max}\) e colorazione \(\chi(G)\) (Cap. 5).
-
Una prima cricca a mano: si parte da un vertice di grado massimo e si aggiungono vertici adiacenti a tutti quelli scelti (Cap. 5).
Formulazioni¶
-
Il modello \(\ILP_{\MCP}\) ha una variabile binaria per vertice e un vincolo \(x_u+x_v\le1\) per ogni coppia di vertici non adiacenti (Cap. 12).
-
\(x_v=\frac12\) per tutti i vertici è ammissibile, quindi \(z(\LP_{\MCP})\ge n/2\): il bound del rilassamento lineare può essere arbitrariamente debole (Cap. 12).
-
Le disuguaglianze di cricca sugli insiemi stabili di \(G\) rafforzano il modello, e il duale del loro rilassamento è un rilassamento del VCP: \(\omega(G)\le z(\LP^{\mathrm{CL}}_{\MCP})\le\chi(G)\) (Cap. 12).