Problemi del corso

Scegli un problema, segui l'esempio illustrato e passa al prossimo.

ClasseSolo completiSolo nelle tracce

36 problemi

Problema 12 di 36

CLIQUE

Dato un grafo e un intero $K$ : esistono $K$ nodi tutti collegati tra loro?

NPNP-completo

Nelle tracce · 8 domande

F02, domanda 3 F04, domanda 1 F04, domanda 2 F07, domanda 6 L18, domanda 6 G20v4, domanda 7 ND, domanda 6 SP, domanda 8

Un esempio, passo dopo passo

1 / 3

Leggi grafo e dimensione. Il grafo ha i vertici A, B, C, D e gli archi AB, AC, BC e CD: un triangolo, con D attaccato a C. Con K = 3 cerchiamo tre vertici collegati a due a due. — 1. Leggi grafo e dimensione
Il grafo ha i vertici $A$ , $B$ , $C$ , $D$ e gli archi $AB$ , $AC$ , $BC$ e $CD$ : un triangolo, con $D$ attaccato a $C$ . Con $K = 3$ cerchiamo tre vertici collegati a due a due.

Scorri l'immagine o usa Avanti.

Una clique è un gruppo di vertici in cui ogni coppia è collegata. Il certificato sono i $K$ vertici scelti: si controllano al più $K(K-1)/2$ coppie.

Il grafo complementare ha gli stessi vertici e inverte gli archi fra vertici distinti: se $A$ e $B$ erano collegati, nel complementare non lo sono; se non lo erano, lo diventano. Non si aggiungono cappi.

Per esempio, il complementare di un triangolo completo su $A$ , $B$ , $C$ ha gli stessi tre vertici e nessun arco. Una clique in $G$ diventa così un insieme indipendente nel complementare di $G$ : cambiano gli archi, i vertici scelti restano gli stessi.

Complemento e collegamenti

Nessun complemento associato.

una clique in $G$ è un insieme indipendente nel grafo complementare

Corollario: CLIQUE e NODE COVER sono NP-completi

Domande e trappole d'esame

F02#3
È vero che CLIQUE non appartiene a NEXP?
NO $\htmlData{term=problem:CLIQUE}{\mathrm{CLIQUE}} \in \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=NEXP}{\mathrm{NEXP}}$ .
F07#6
$\htmlData{term=problem:CLIQUE}{\mathrm{CLIQUE}} \in \htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}}$ ?
SÌ $\htmlData{term=Σ1}{\Sigma_1^{\mathrm{P}}} = \htmlData{term=NP}{\mathrm{NP}}$ . Ripetuta in F04#2.
L18#6
CLIQUE si può risolvere in $O(2^{n/2})$ ?
SÌ $m$ è il numero di nodi e $n$ la lunghezza dell'intero input in bit: il limite richiesto usa $n$ , non $m$ .

Con la codifica tramite matrice di adiacenza, un grafo di $m$ nodi richiede $m$ righe e $m$ colonne: almeno $m^2$ bit, uno per ogni cella. Quindi $n \ge m^2$ e $m \le \sqrt{n}$ .

L'algoritmo prova tutti i $2^m$ gruppi di nodi e per ognuno controlla che contenga almeno $K$ nodi e che ogni coppia sia collegata. Il controllo richiede tempo polinomiale, quindi il totale è al più $2^{\sqrt{n}} \cdot \mathrm{poly}(n)$ .

Questo basta perché, per $n$ abbastanza grande, $\sqrt{n}$ cresce molto più lentamente di $n/2$ . Anche con il costo polinomiale dei controlli il tempo resta entro $O(2^{n/2})$ : infatti $\sqrt{n} + k \log _2 n \le n/2$ per ogni $k$ fissato, da un certo $n$ in poi.

Per esempio, con 10 nodi la sola matrice ha 100 celle: i gruppi da provare sono $2^{10} = 1.024$ , mentre $2^{n/2}$ è almeno $2^{50}$ .
ND#6
CLIQUE è PH-hard?
altro: solo se $\mathrm{PH} = \mathrm{NP}$ PH-hard darebbe $\htmlData{term=PH}{\mathrm{PH}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$ : collasso al primo livello.
G20v4#7
È vero che CLIQUE non appartiene a $\htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}$ ?
NO $\htmlData{term=problem:CLIQUE}{\mathrm{CLIQUE}} \in \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=Π2}{\Pi_2^{\mathrm{P}}} \subseteq \htmlData{term=Π4}{\Pi_4^{\mathrm{P}}}$ .

Problemi del corso

1. Leggi grafo e dimensione

2. Scegli i vertici

3. Verifica ogni coppia