Clique massima: limiti dell'approssimazione¶

Parte 5 · Algoritmi di approssimazione · Capitolo 38 · Dispensa, volume 5 (PDF) · Slide · Esercizi: Clique massima (MCP)

Prerequisiti

Da questo modulo, il capitolo «Principi degli algoritmi di approssimazione»: rapporto di prestazione per un problema di massimo, algoritmo di \(\alpha\)-approssimazione, PTAS.
Da questo modulo, il capitolo «Problemi di clique»: le definizioni del MCP e del MSSP, il numero di clique \(\omega(G)\), il grafo complementare e \(\omega(G)=\alpha(\overline{G})\).
Da questo modulo, il capitolo «Colorazione dei vertici: limiti dell'approssimazione»: i grafi planari e il bound \(m\le 3n-6\).

Obiettivi

Al termine di questo capitolo saremo in grado di:

costruire il prodotto forte di due grafi e dimostrare \(\omega(G\boxtimes H)=\omega(G)\,\omega(H)\);
dimostrare che un algoritmo a rapporto costante per il MCP ne darebbe uno per ogni rapporto costante;
enunciare i risultati di Håstad e Zuckerman, e concludere che il MCP e il MSSP non sono approssimabili;
risolvere il MCP all'ottimo sui grafi planari e sui grafi di grado limitato, e approssimare il MSSP sui grafi di grado limitato.

Il problema di questo capitolo è il problema della clique massima (MCP): la sua definizione e le sue ipotesi sono nella sua pagina.

38.1 Notazione¶

Come nella pagina del problema, \(G=(V,E)\) è un grafo semplice con \(n\) vertici e \(m\) spigoli, \(N(v)\) è l'insieme dei vicini di \(v\) e \(\Delta(G)\) il grado massimo. Il valore ottimo del MCP è il numero di clique, \(z(I)=\omega(G)\), e quello del MSSP è il numero di stabilità \(\alpha(G)\).
Richiamo. Come nel capitolo «Principi degli algoritmi di approssimazione», \(\mathscr{A}(I)\) è il numero di vertici della clique restituita dall'algoritmo \(\mathscr{A}\). Il MCP è un problema di massimo, quindi

\[ \mathscr{A}(I) \le \omega(G) ~~~~~~~\text{e}~~~~~~~ \frac{\omega(G)}{\mathscr{A}(I)} \ge 1 \]

per ogni istanza \(I\).
Un singolo vertice è una clique, quindi il rapporto \(n\) è banale. Questo capitolo mostra che un algoritmo polinomiale non può fare molto meglio su tutti i grafi, e poi le classi di grafi su cui può.

38.2 Il MCP non è approssimabile¶

38.2.1 Il prodotto forte¶

Definizione 38.1: prodotto forte

Il prodotto forte di due grafi \(G=(V,E)\) e \(H=(W,F)\) è il grafo \(G\boxtimes H\) con insieme dei vertici \(V\times W\), in cui due vertici distinti \((u,x)\) e \((v,y)\) sono adiacenti se e solo se

\[ \big(u=v \ \text{ oppure }\ \{u,v\}\in E\big) \quad\text{e}\quad \big(x=y \ \text{ oppure }\ \{x,y\}\in F\big). \]

\(G\boxtimes H\) ha \(|V|\,|W|\) vertici e si costruisce in tempo polinomiale nella dimensione di \(G\) e \(H\). In particolare \(G\boxtimes G\) ha \(n^2\) vertici.
Per un insieme \(K\subseteq V\times W\), la proiezione è \(p(K)=\{u\in V:(u,x)\in K \text{ per qualche } x\}\), e la fibra di \(u\in p(K)\) è \(K_u=\{x\in W:(u,x)\in K\}\).

Proposizione 38.2

Per ogni coppia di grafi \(G\) e \(H\):

se \(K\subseteq V\times W\) è una clique di \(G\boxtimes H\), allora \(p(K)\) è una clique di \(G\), ogni fibra \(K_u\) è una clique di \(H\), e \(|K|\le|p(K)|\cdot\max_{u}|K_u|\);
\(\omega(G\boxtimes H)=\omega(G)\,\omega(H)\).

Dimostrazione

Parte 1. Siano \(u\neq v\) in \(p(K)\), con \((u,x),(v,y)\in K\). Questi due vertici sono adiacenti e \(u\neq v\), quindi \(\{u,v\}\in E\): \(p(K)\) è una clique. Siano \(x\neq y\) in \(K_u\): \((u,x)\) e \((u,y)\) sono adiacenti, quindi \(\{x,y\}\in F\), e \(K_u\) è una clique. Le fibre partizionano \(K\), quindi

\[ |K| \;=\; \sum_{u\in p(K)} |K_u| \;\le\; |p(K)|\cdot\max_{u}|K_u| . \]

Parte 2. Se \(K_G\) e \(K_H\) sono clique massime di \(G\) e \(H\), ogni coppia di vertici distinti di \(K_G\times K_H\) soddisfa la definizione, quindi \(\omega(G\boxtimes H)\ge\omega(G)\,\omega(H)\). Viceversa, per la Parte 1 ogni clique \(K\) di \(G\boxtimes H\) ha \(|K|\le|p(K)|\cdot\max_u|K_u|\le\omega(G)\,\omega(H)\). □

Anche il prodotto lessicografico soddisfa \(\omega(G[H])=\omega(G)\,\omega(H)\); usiamo il prodotto forte, la cui definizione è simmetrica nei due grafi.

38.2.2 Un rapporto costante darebbe ogni rapporto costante¶

La Parte 1 della Proposizione 38.2 è costruttiva: da una clique \(K\) di \(G\boxtimes G\), \(p(K)\) oppure la fibra più grande è una clique di \(G\) con almeno \(\sqrt{|K|}\) vertici, perché il prodotto delle loro dimensioni è almeno \(|K|\). Entrambe si calcolano in tempo polinomiale.

Teorema 38.3

Se il MCP ha un algoritmo polinomiale di \(\alpha\)-approssimazione per qualche costante \(\alpha\ge1\), allora ha un algoritmo polinomiale di \(\beta\)-approssimazione per ogni costante \(\beta>1\).

Dimostrazione

Sia \(\mathscr{A}\) un algoritmo polinomiale di \(\alpha\)-approssimazione, e definiamo l'algoritmo \(\mathscr{B}\):

costruire \(G\boxtimes G\) ed eseguire \(\mathscr{A}\) su di esso, ottenendo una clique \(K\);
restituire la più grande fra \(p(K)\) e la fibra più grande di \(K\), una clique di \(G\) con almeno \(\sqrt{|K|}\) vertici.

Per la Proposizione 38.2, \(\omega(G\boxtimes G)=\omega(G)^2\), quindi \(|K|\ge\frac{\omega(G)^2}{\alpha}\) e

\[ \mathscr{B}(I) \;\ge\; \sqrt{|K|} \;\ge\; \frac{\omega(G)}{\sqrt{\alpha}} : \]

\(\mathscr{B}\) è un algoritmo polinomiale di \(\sqrt{\alpha}\)-approssimazione. Applicando la costruzione \(t\) volte si ottiene il rapporto \(\alpha^{1/2^t}\), con \(\mathscr{A}\) eseguito su un grafo con \(n^{2^t}\) vertici. Scegliamo la costante \(t\) con \(2^t\ge\frac{\ln\alpha}{\ln\beta}\): allora \(\alpha^{1/2^t}\le\beta\), e \(n^{2^t}\) è un polinomio. □

In altre parole, il MCP ha un algoritmo a rapporto costante se e solo se ha un PTAS: il prodotto forte amplifica qualunque rapporto costante. Il tempo di esecuzione cresce come una potenza \(n^{2^t}\), che è polinomiale solo perché \(t\) è una costante.

38.2.3 I risultati di Håstad e Zuckerman¶

Il lato negativo è noto, e lo enunciamo senza dimostrazione: usa le dimostrazioni verificabili probabilisticamente.

Teorema 38.4: Håstad, 1999; Zuckerman, 2007

Per ogni \(\varepsilon>0\), se \(P\neq NP\), nessun algoritmo polinomiale \(\mathscr{A}\) per il MCP soddisfa, per ogni grafo \(G\) con \(n\) vertici,

\[ \frac{\omega(G)}{\mathscr{A}(I)} \;\le\; n^{1-\varepsilon} . \]

Håstad (1999) ha dimostrato il teorema nell'ipotesi che i problemi NP non si possano risolvere in tempo polinomiale randomizzato (\(NP\neq ZPP\)); Zuckerman (2007) lo ha dimostrato nell'ipotesi \(P\neq NP\).
Come per il VCP, il teorema esclude ogni rapporto costante: un algoritmo di \(\alpha\)-approssimazione ha rapporto al più \(\alpha<n^{1/2}\) sui grafi con \(n>\alpha^2\) vertici, e i grafi più piccoli si risolvono per enumerazione in tempo costante. Insieme al Teorema 38.3: a meno che \(P=NP\), il MCP non ha né un rapporto costante né un PTAS.

Il MCP non è approssimabile: a meno che \(P=NP\), nessun algoritmo polinomiale ha una garanzia di prestazione costante, e nemmeno una garanzia della forma \(n^{1-\varepsilon}\). Esistono risultati positivi solo su classi particolari di grafi.

38.3 Casi particolari¶

38.3.1 Grafi planari¶

Proposizione 38.5

Ogni grafo planare ha \(\omega(G)\le 4\), e sui grafi planari il MCP si risolve all'ottimo in tempo \(O(n^4)\).

Dimostrazione

Un sottografo di un grafo planare è planare. Il grafo completo con \(5\) vertici ha \(10\) spigoli, più di \(3\cdot5-6=9\), quindi non è planare, e un grafo planare non ha clique con \(5\) vertici. I sottoinsiemi di al più \(4\) vertici sono \(O(n^4)\), e ciascuno si verifica in tempo costante. □

38.3.2 Grafi di grado massimo limitato¶

Proposizione 38.6

Ogni grafo ha \(\omega(G)\le\Delta(G)+1\), e il MCP si risolve all'ottimo in tempo \(O(n\,2^{\Delta}\,\Delta^2)\), con \(\Delta=\Delta(G)\).

Dimostrazione

Una clique che contiene il vertice \(v\) è contenuta in \(\{v\}\cup N(v)\), che ha al più \(\Delta+1\) vertici. Per ogni vertice \(v\), enumeriamo i \(2^{\deg(v)}\le 2^\Delta\) sottoinsiemi \(S\subseteq N(v)\) e teniamo il più grande \(\{v\}\cup S\) che sia una clique; verificare le coppie di \(S\) richiede tempo \(O(\Delta^2)\). Ogni clique massima si trova a partire da uno qualsiasi dei suoi vertici. □

Il tempo è polinomiale per ogni \(\Delta\) fissato, e anche quando \(\Delta\le\log_2 n\), perché allora \(2^\Delta\le n\).

38.3.3 Il problema dell'insieme stabile massimo¶

Per \(\omega(G)=\alpha(\overline{G})\) (capitolo «Problemi di clique»), un insieme stabile di \(G\) è una clique di \(\overline{G}\), che si costruisce in tempo \(O(n^2)\) e ha lo stesso \(n\).
Un algoritmo con rapporto \(\rho(n)\) per uno dei due problemi, applicato al grafo complementare, ha lo stesso rapporto \(\rho(n)\) per l'altro.

Corollario 38.7

Per ogni \(\varepsilon>0\), se \(P\neq NP\), nessun algoritmo polinomiale per il MSSP ha rapporto \(\frac{\alpha(G)}{\mathscr{A}(I)}\le n^{1-\varepsilon}\) su ogni grafo. In particolare, il MSSP non ha un rapporto costante.

I casi particolari non si trasferiscono: il complementare di un grafo planare, o di un grafo di grado limitato, è denso. Su quelle classi il MSSP resta NP-difficile, ma è approssimabile.

Proposizione 38.8

Su ogni grafo, un insieme stabile massimale \(S\) (a cui non si può aggiungere nessun vertice) ha \(|S|\ge\frac{n}{\Delta(G)+1}\). Quindi l'algoritmo greedy che aggiunge vertici finché è possibile soddisfa

\[ \frac{\alpha(G)}{|S|} \;\le\; \Delta(G)+1 . \]

Dimostrazione

Ogni vertice fuori da \(S\) ha un vicino in \(S\), altrimenti si potrebbe aggiungere. Quindi \(V=\bigcup_{v\in S}\big(\{v\}\cup N(v)\big)\), e \(n\le|S|\,(\Delta(G)+1)\). Poiché \(\alpha(G)\le n\), il rapporto è al più \(\frac{n}{|S|}\le\Delta(G)+1\). □

Sui grafi di grado massimo al più un \(\Delta\) fissato questo è un rapporto costante. Sui grafi planari il MSSP ha addirittura un PTAS (Baker, 1994).

38.4 Esempio¶

Esempio 38.1: Prodotto forte ed enumerazione sull'istanza di riferimento del MCP

L'istanza di riferimento del MCP è il ciclo \(1,2,\dots,7,1\) con la corda \(\{1,3\}\): \(n=7\), \(m=8\), \(\Delta(G)=3\) e \(\omega(G)=3\), con l'unica clique massima \(\{1,2,3\}\) (in rosso).

Figura 1

Prodotto forte. \(G\boxtimes G\) ha \(7^2=49\) vertici e \(240\) spigoli, e \(\omega(G\boxtimes G)=3^2=9\), raggiunto da \(\{1,2,3\}\times\{1,2,3\}\).
Supponiamo che un algoritmo restituisca su \(G\boxtimes G\) la clique \(K=\{1,2,3\}\times\{4,5\}\), con \(|K|=6\). La sua proiezione \(p(K)=\{1,2,3\}\) e le sue fibre \(K_u=\{4,5\}\) sono clique di \(G\); la più grande ha \(3\ge\sqrt6\) vertici.
Grado limitato. L'enumerazione della Proposizione 38.6 esamina \(\sum_v 2^{\deg(v)}=2^3+2^2+2^3+4\cdot 2^2=36\) sottoinsiemi, e trova \(\{1,2,3\}\) dai vertici \(1\), \(2\) e \(3\).
Planarità. Il grafo è planare, come mostra la figura, e \(\omega(G)=3\le 4\).

38.5 Fonti¶

M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979 (l'auto-miglioramento del MCP con i prodotti di grafi).
J. Håstad, Clique is hard to approximate within \(n^{1-\varepsilon}\), Acta Mathematica 182(1):105–142, 1999.
D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory of Computing 3:103–128, 2007.
B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM 41(1):153–180, 1994.

38.6 Errori tipici¶

Attenzione

Invertire il rapporto. Il MCP è un problema di massimo: il rapporto è \(\frac{\omega(G)}{\mathscr{A}(I)}\), almeno \(1\).
Iterare il prodotto un numero di volte che cresce con \(n\). Il grafo dopo \(t\) prodotti ha \(n^{2^t}\) vertici: è polinomiale solo per \(t\) costante, quindi l'amplificazione dà ogni rapporto costante, non il rapporto \(1\).
Trasferire i casi particolari al MSSP. Il complementare di un grafo planare non è planare: il MCP è facile sui grafi planari, il MSSP lì è NP-difficile.
Confondere il bound \(\Delta(G)+1\) del MCP con quello del MSSP. Per il MCP, \(\omega(G)\le\Delta(G)+1\) limita l'ottimo e rende veloce l'enumerazione; per il MSSP, \(\Delta(G)+1\) limita il rapporto di un insieme stabile massimale.

38.7 In sintesi¶

In sintesi

Il prodotto forte eleva al quadrato il numero di clique, e una clique del prodotto restituisce una clique di \(G\) di dimensione almeno pari alla radice quadrata della sua: un rapporto costante per il MCP darebbe ogni rapporto costante.
Per i risultati di Håstad e Zuckerman, a meno che \(P=NP\) non è possibile nemmeno il rapporto \(n^{1-\varepsilon}\): il MCP non è approssimabile, e nemmeno il MSSP, attraverso il grafo complementare.
Sui grafi planari e sui grafi di grado limitato il MCP si risolve all'ottimo per enumerazione; sui grafi di grado limitato un insieme stabile massimale ha rapporto al più \(\Delta(G)+1\) per il MSSP.

problema e grafi	algoritmo	risultato
MCP, tutti i grafi	polinomiale	nessun rapporto costante, salvo \(P=NP\)
MCP, planari	enumerazione	esatto, \(\omega(G)\le4\)
MCP, grado \(\le\Delta\)	enumerazione	esatto, \(O(n\,2^\Delta\Delta^2)\)
MSSP, tutti i grafi	polinomiale	nessun rapporto costante, salvo \(P=NP\)
MSSP, grado \(\le\Delta\)	stabile massimale	rapporto \(\le\Delta+1\)

Cruscotto dell'istanza di riferimento.

Istanza	Upper bound	Valore trovato	Valore ottimo
ciclo con una corda	\(\Delta(G)+1=4\)	\(3\), enumerazione	\(3\)

Esercizi su questo capitolo: Clique massima (MCP)