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. Archi AB, AC, BC, CD. Cerchiamo K = 3 vertici collegati a coppie. — 1. Leggi grafo e dimensione
Archi $AB$ , $AC$ , $BC$ , $CD$ . Cerchiamo $K = 3$ vertici collegati a coppie.

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.

Grafo complementare: si mantengono tutti i vertici e si invertono gli archi fra vertici distinti. Se $A$ e $B$ erano collegati, nel complementare non lo sono; se non erano collegati, 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. Quindi una clique in $G$ diventa un insieme indipendente nel complementare di $G$ : gli archi cambiano, 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; $n$ è la lunghezza dell’intero input in bit. Il limite richiesto usa $n$ , non $m$ .

1. Quanto è grande l’input? 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}$ .

2. Che algoritmo usiamo? Proviamo tutti i $2^m$ gruppi di nodi. Per ogni gruppo controlliamo 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)$ .

3. Perché basta? Per $n$ abbastanza grande, $\sqrt{n}$ cresce molto più lentamente di $n/2$ . Anche includendo il costo polinomiale dei controlli, il tempo rimane 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.

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}$ . La differenza nasce dal fatto che $n$ conta i bit della descrizione.
ND#6
CLIQUE è PH-hard?
altro: solo se $\htmlData{term=PH}{\mathrm{PH}} = \htmlData{term=NP}{\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