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.

Definizione

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 ha una copertura tramite vertici di cardinalità $k$ se e solo se il grafo ha un insieme indipendente di cardinalità $n-k$ . In questo senso, i due problemi sono duali.

Trattabilità

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

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 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 $2^{o({\sqrt {k}})}n^{{\mathcal {O}}(1)}$ .^[3]

Approssimabilità

È 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

^ M. R. Garey, D. S. Johnson e L. Stockmeyer, Some simplified NP-complete problems, in Proceedings of the sixth annual ACM symposium on Theory of computing, 1974, 47–63.
^ 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.
^ Flum, J., Grohe, M., Parameterized Complexity Theory, Springer, 2006, ISBN 978-3-540-29952-3. URL consultato il 3 maggio 2019 (archiviato dall'url originale il 18 novembre 2007).
^ George Karakostas. A better approximation ratio for the Vertex Cover problem. ECCC Report, TR04-084, 2004.
^ I. Dinur and S. Safra. On the Hardness of Approximating Minimum Vertex-Cover Archiviato il 20 settembre 2009 in Internet Archive.. Annals of Mathematics, 162(1):439-485, 2005. (Preliminary version in STOC 2002, titled "On the Importance of Being Biased").