Paola Festa » 18.Il Problema del Vertex Cover Minimo di un Grafo

Il Problema del Vertex Cover Minimo, 1

Dato un grafo non orientato G=(V,E), un sottoinsieme V’ non proprio di V è detto vertex cover per G se per ogni arco di G almeno uno dei vertici ad esso incidenti appartiene a V’.
Formalmente, tale proprietà di V’ è espressa come segue.
Definizione. V’ è un vertex cover per il grafo G=(V,E) se per ogni arco [i,j] in E, almeno una delle seguenti condizioni è verificata:

i appartiene a V’;
j appartiene a V’.

Dato un grafo non orientato G=(V,E), il Problema del Vertex Cover Minimo (VC) consiste nel trovare un vertex cover per G di cardinalità minima.

VC è un problema “difficile” dal punto di vista computazionale.
Studieremo in quanto segue la sua descrizione logico-matematica ed un algoritmo 2-approssimato di tipo random.

Il Problema del Vertex Cover Minimo, 2

Introducendo le seguenti $\vert V\vert=n$ variabili di decisione

$\forall\ j=1,2,\ldots,n,\\ x_j=\left\{ \begin{array}{lll}1& \mbox{{\rm se $j\in V'$}}\\ 0&\mbox{{\rm altrimenti,}}\end{array} \right.$

si ottiene la seguente formulazione matematica per il Problema del Vertex Cover Minimo di G:
$\begin{array}{llll} \mbox{(VC)} & \mbox{{\rm min}} & \displaystyle{\sum_{j=1}^n x_j}\\ & \mbox{{\rm s.a}} \\ & & x_i+x_j \geq 1, & \forall\ [i,j]\in E \\ \\ & & x_j\in\{0,1\}, & j=1,2,\ldots,n. \end{array}$

Il Problema del Vertex Cover Minimo, 3

Come già sottolineato, il Problema del Vertex Cover Minimo di un grafo G è un problema “difficile”, per cui a tutt’oggi un qualunque algoritmo esatto per esso ha complessità computazionale superpolinomiale.
Tuttavia , è possibile individuare una soluzione approssimata in tempo polinomiale.

In quanto segue verrà descritto un algoritmo polinomiale di approssimazione che, preso in input un grafo non orientato G=(V,E), trova con complessità $O(\vert E\vert)$ un vertex cover V’ per G di taglia al più due volte la taglia di un vertex cover ottimo V*, ossia
$\vert V'\vert\leq 2\ \vert V^*\vert.$

Il Problema del Vertex Cover Minimo, 4

2-approx-vc: un algoritmo polinomiale di approssimazione per il Problema del Vertex Cover Minimo di un grafo.

$\fbox{\begin{minipage}[h]{11cm} \footnotesize{ \begin{tt} {\bf algoritmo} {$2$-approx-vc} ($V$,$E$)\\ $1$\hspace*{0.5truecm} $V':=\emptyset$; $E':=E$;\\ $2$\hspace*{0.5truecm} {\bf while} ($E'\not=\emptyset$) {\bf do} \\ $3$\hspace*{1truecm} $[i,j]=$select($E'$);\hspace*{0.2truecm} \mbox{/* seleziona da $E'$ un arco a caso */}\\ $4$\hspace*{1truecm} $V':=V'\cup\{i,j\}$; \\ $5$\hspace*{1truecm} $E':=E'\setminus\{[u,v]\ \vert\ v=i\ \mbox{o}\ u=j\}$; \\ $6$\hspace*{0.5truecm} {\bf endwhile} \\ $7$\hspace*{0.5truecm} {\bf return} ($V'$); \\ {\bf end} {$2$-approx-vc} \hspace*{0.2truecm} \mbox{/*$O(\vert E\vert)=O(m)$ */} \end{tt} } \end{minipage}}$

Il Problema del Vertex Cover Minimo, 5

Teorema. L’insieme V’ restituito in output da 2-approx-vc è un vertex cover per G tale che
$\vert V'\vert\leq 2\ \vert V^*\vert.$
Dimostrazione. V’ restituito in output è un vertex cover per G per costruzione.
Indichiamo con A l’insieme degli archi selezionati a caso da E’ (linea 3).
Per ogni arco [i,j] in A, i e j sono aggiunti a V’ (linea 4), per cui si ha che |V’|=2|A|.
Inoltre, vengono rimossi da E’ tutti gli archi incidenti in almeno uno fra i vertici i e j (linea 5), per cui due archi in A non possono essere adiacenti. Conseguenza di quest’ultima osservazione è che
$\vert A\vert\leq\vert V^*\vert,$
da cui la tesi.

Il Problema del Vertex Cover Minimo, 6

Esempio 1. Si applichi 2-approx-vc per trovare un vertex cover approssimato per il grafo riportato in Figura (a).
Inizialmente, E’:=E.

I it.: supponiamo di scegliere da E’ l’arco [1,2].
V’={1,2}, mentre E’={[4,3]}.

II it.: l’unico arco che può essere selezionato da E’ è [4,3].
V’= {1,2,3,4}=V, mentre E’ diventa un ins. vuoto –> STOP.

Nota: |V’|=2 |V*|.

(a) un grafo non orientato avente 4 nodi e 5 archi; (b) un grafo non orientato avente 4 nodi e 5 archi. Disegnata da Paola Festa

Il Problema del Vertex Cover Minimo, 7

Se applicassimo 2-approx-vc per trovare un vertex cover approssimato per il grafo riportato in Figura (b) e alla I it. l’algoritmo scegliesse ancora una volta l’arco [1,2], allora il vertex cover V’={1,2} restituito in output sarebbe un vertex cover ottimo.