Problema di copertura dei vertici

Da Wikipedia, l'enciclopedia libera.

Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei problemi completi non deterministici, 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 Richard Karp. È spesso usato in complessità computazionale per dimostrare l'NP-completezza di problemi più complicati.

Definizione[modifica | modifica sorgente]

Una copertura tramite vertici di un grafo non orientato G = (V, E) è un sottoinsieme S dei suoi vertici tale che ogni arco ha almeno un'estremità in 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  \bar S = V \setminus S è un insieme indipendente. Segue che un grafo con n vertici avente una copertura tramite vertici di cardinalità k se e solo se il grafo ha in insieme indipendente di cardinalità n-k. In questo senso, i due problemi sono duali.

Trattabilità[modifica | modifica sorgente]

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.

Trattabilità a parametro fisso[modifica | modifica sorgente]

Nonostante il problema della copertura tramite vertici sia NP-completo, un algoritmo di forza bruta può risolvere il problema in tempo 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 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 2^{o(k)} n^{\mathcal O(1)}.

In un grafo planare, comunque, una copertura tramite vertici di cardinalità k può essere trovata in tempo 2^{\mathcal O(\sqrt{k})} n^2, cioè, il problema è sub-esponenziale rispetto alla trattabilità a parametro fisso. Questo algortimo è 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 2^{o(\sqrt{k})} n^{\mathcal O(1)}.[3]

Approssimabilità[modifica | modifica sorgente]

È 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 2 - \Theta \left( \frac{1}{\sqrt{\log |V|}}   \right) per un dato 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.

Note[modifica | modifica sorgente]

  1. ^ Some simplified NP-complete problems in Proceedings of the sixth annual ACM symposium on Theory of computing, 1974, pp. 47–63.
  2. ^ M. R. Garey, D. S. Johnson, The rectilinear Steiner tree problem is NP-complete in SIAM Journal on Applied Mathematics, vol. 32, nº 4, 1977, pp. 826–834, DOI:10.1137/0132071.
  3. ^ Flum, J., Grohe, M., Parameterized Complexity Theory, Springer, 2006, ISBN 978-3-540-29952-3.
  4. ^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
  5. ^ I. Dinur and S. Safra. On the Hardness of Approximating Minimum Vertex-Cover. Annals of Mathematics, 162(1):439-485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]