Problema dell'insieme stabile massimo (MSSP)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi di cricca · Catalogo (PDF)

Definizione 1: Problema dell'insieme stabile massimo

Sia \(G=(V,E)\) un grafo.

1. Un insieme stabile (detto anche insieme indipendente) è un sottoinsieme \(Q \subseteq V\) di vertici a due a due non adiacenti: \(\{u,v\} \notin E\) per ogni \(u,v \in Q\) con \(u \neq v\).

2. Il problema dell'insieme stabile massimo (MSSP) chiede di trovare un insieme stabile di \(G\) il cui numero di vertici sia massimo. Il suo valore ottimo è il numero di stabilità \(\alpha(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	Esercizio 4.3; Cap. 5 (2 esercizi); Esercizio 12.6; Cap. 38 (2 esercizi)