Vertex cover (semplice e pesato)

NP-arduo

Dato un grafo non orientato G=(V,E)G=(V,E), un vertex cover è un insieme di nodi V′⊆VV'\subseteq V che tocca tutti gli archi: per ogni [i,j]∈E[i,j]\in E, i∈V′i\in V' oppure j∈V′j\in V'. Il problema semplice chiede un vertex cover con il minor numero di nodi. Nel pesato ogni nodo ha un peso wj≥0w_j\ge 0 e si cerca il vertex cover di peso totale minimo.

min⁡ ∑j=1nwjxj(wj=1 nel caso semplice)s.a. xi+xj≥1∀ [i,j]∈Exj∈{0,1}j=1,…,n\begin{aligned} \min\ & \sum_{j=1}^{n}w_jx_j && (w_j=1 \text{ nel caso semplice})\\ \text{s.a.}\ & x_i+x_j\ge 1 && \forall\,[i,j]\in E\\ & x_j\in\{0,1\} && j=1,\dots,n \end{aligned}

Perché è difficile

Il problema è NP-arduo, quindi non si conosce un algoritmo esatto polinomiale. Si approssima: 2-approx-vc trova in O(m)O(m) un vertex cover con al più il doppio dei nodi dell'ottimo.

Da ricordare

  • ∣V′∣≤2∣V∗∣|V'|\le 2|V^*| perché gli archi scelti non hanno estremi in comune: l'ottimo ne copre ciascuno con un nodo diverso, l'algoritmo con due.
  • Dopo aver scelto [i,j][i,j] si tolgono tutti gli archi che toccano ii o jj.
  • La garanzia vale solo nel caso semplice: nel pesato l'algoritmo ignora i pesi.

Algoritmi

Fonti: dispensa §4.2, §4.2.1 e §4.2.2, Teorema 4.2.1, appunti Lezione 9, §4, appunti Lezione 1, §6.