Problema di copertura dei vertici

Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei più difficili problemi risolvibili non-deterministicamente in tempo polinomiale, assieme al problema del commesso viaggiatore, il knapsack problem, ecc.

Questa classe di problemi è detta NP-completo, si dice cioè che il vertex cover o problema di copertura dei vertici è un problema NP-completo. È utile al riguardo la dimostrazione di equivalenza fra tutti i problemi NP-completo, come premesso. Mediante questi problemi si ottengono, ad esempio, modelli per la logistica o per il calcolo delle spese nella produzione. Il problema complementare al vertex-cover è detto copertura degli spigoli o edge cover.

In informatica, il problema di copertura tramite vertici è un problema NP-completo e fu uno dei 21 problemi NP-completi di Karp. È spesso usato in complessità computazionale per dimostrare l'NP-hardness di problemi più complicati.

Una copertura tramite vertici di un grafo non orientato ${\displaystyle G=(V,E)}$ è un sottoinsieme ${\displaystyle S}$ dei suoi vertici tale che ogni arco ha almeno un'estremità in ${\displaystyle S}$.

Il problema di copertura tramite vertici è il problema di ottimizzazione combinatoria di trovare la più piccola copertura tramite vertici in un grafo.

La copertura tramite vertici è strettamente correlata al massimo insieme indipendente. Un insieme di vertici è una copertura tramite vertici se e solo se il suo complemento ${\displaystyle {\bar {S}}=V\setminus S}$ è un insieme indipendente. Segue che un grafo con ${\displaystyle n}$ vertici ha una copertura tramite vertici di cardinalità ${\displaystyle k}$ se e solo se il grafo ha un insieme indipendente di cardinalità ${\displaystyle n-k}$. In questo senso, i due problemi sono duali.

Il problema di decisione associato al problema della copertura tramite vertici è NP-completo, il che significa che è difficile che ci sia un algoritmo efficiente che lo risolva in modo esatto. L'NP completezza può essere dimostrata per riduzione da 3SAT o, come fece Karp, per riduzione dal problema della cricca. La copertura tramite vertici rimane NP-completa anche nel grafi cubici^[1] ed in grafi planari di grado almeno 3 ^[2].

In un grafo bipartito, l'equivalenza tra la copertura tramite vertici e l'accoppiamento massimale descritto dal teorema di König permette al problema della copertura tramite vertici in grafi bipartiti di essere risolto in tempo polinomiale.

Nonostante il problema della copertura tramite vertici sia NP-completo, un algoritmo di forza bruta può risolvere il problema in tempo ${\displaystyle 2^{{\mathcal {O}}(k)}n^{{\mathcal {O}}(1)}}$. La copertura dei vertici è quindi trattabile a parametro fisso, e se siamo interessati solo a piccoli valori di ${\displaystyle k}$, possiamo risolvere il problema in tempo polinomiale. La strategia dell'algoritmo a forza bruta è di scegliere un vertice e fare salti ricorsivi, con due casi ad ogni passo: inserire il vertice corrente o tutti i vertici ad esso adiacenti nella copertura tramite vertici. Sotto assunzioni ragionevoli di teoria della complessità computazionale, questo tempo di esecuzione non può essere migliorato a ${\displaystyle 2^{o(k)}n^{{\mathcal {O}}(1)}}$.

In un grafo planare, comunque, una copertura tramite vertici di cardinalità ${\displaystyle k}$ può essere trovata in tempo ${\displaystyle 2^{{\mathcal {O}}({\sqrt {k}})}n^{2}}$, cioè, il problema è sub-esponenziale rispetto alla trattabilità a parametro fisso. Questo algoritmo è di nuovo ottimo, nel senso che, sotto le stesse assunzioni di teoria della complessità computazionale, nessun algoritmo può risolvere il problema della copertura tramite vertici in grafi planari in tempo ${\displaystyle 2^{o({\sqrt {k}})}n^{{\mathcal {O}}(1)}}$.^[3]

È possibile trovare un algoritmo di approssimazione di fattore 2 prendendo ripetutamente entrambi gli estremi di un arco nella copertura tramite vertici, quindi rimuovendoli dal grafo. Nessuna approssimazione con fattori costanti migliori è nota; il problema è APX-complete, cioè non può essere approssimato con precisione arbitraria. In particolare, la copertura minima tramite vertici è approssimabile in ${\displaystyle 2-\Theta \left({\frac {1}{\sqrt {\log |V|}}}\right)}$ per un dato ${\displaystyle V\geq 2}$ ^[4] ma non può essere approssimato di un fattore di 1.3606 per qualunque grado dei vertici sufficientemente grande a meno che P=NP.^[5]

Nonostante trovare una copertura tramite vertici di cardinalità minima è equivalente a trovare un insieme indipendente di cardinalità massima, i due problemi non sono equivalenti in quanto ad approssimabilità. Il problema dell'insieme indipendente non ha approssimazioni a fattori costanti a meno che P = NP.

• Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 35.1, pp. 1024–1027.

• Covering (teoria dei grafi)
• Hitting set, una naturale generalizzazione per ipergrafi.

• Wikimedia Commons contiene immagini o altri file su problema di copertura dei vertici

• A compendium of NP optimization problems, su nada.kth.se.
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring, su nlsde.buaa.edu.cn. URL consultato il 21 dicembre 2008 (archiviato dall'url originale il 29 maggio 2013).

Portale Informatica

Portale Matematica