Cobertura de vèrtiços

En teoria de grafos, una cobertura de vèrtiços (a voltes, cobertura de nodos) d'un grafo és un conjunt de vèrtiços que inclou a lo manco un extrem de cada aresta del grafo.

En ciències de la computació, el problema de trobar una cobertura mínima de vèrtiços és un problema d'optimisació clàssic. És NP-difícil, per lo que no pot resoldre's en un algoritme de temps polinòmic si P ≠ NP. Ademés, és difícil d'aproximar: no pot aproximar-se fins a un factor menor que 2 si la conjectura del joc únic és verdadera. Per un atre costat, té vàries aproximacions simples de 2 factors. És un eixemple típic d'un problema d'optimisació NP-difícil que té un algoritme d'aproximació. El seu versió de decisió, el problema de cobertura de vèrtiços, va ser un dels vintiun problemes NP-complets de Karp i, per lo tant, és un problema clàssic NP-complet en teoria de la complexitat computacional. Ademés, el problema de cobertura de vèrtiços és manejable en paràmetros fixos i un problema central en la teoria de la complexitat parametrizada.

El problema de cobertura mínima de vèrtiços pot formular-se com un cas de programació llineal semi sancer, que el seu programa llineal dual és el problema de màxima coincidència.

Els problemes de cobertura de vèrtiços s'han generalisat als hipergrafos; vore cobertes de vèrtiç en hipergrafos.

Definició

Formalment, una cobertura de vèrtiços $V^{'}$ d'un grafo no dirigit $G = (V, E)$ és un subconjunt de $V$ tal que $(u v \in E) \Rightarrow (u \in V^{'} \lor v \in V^{'})$ , és dir, és un conjunt de vèrtiços $V^{'}$ a on cada aresta té a lo manco un extrem en la cobertura de vèrtiços $V^{'}$ . Es diu que dit conjunt cobrix les arestes de $G$ . La figura superior mostra dos eixemples de cobertura de vèrtiços, en les cobertura de vèrtiços $V^{'}$ marcades en roig.

Una cobertura mínima de vèrtiços és una cobertura de vèrtiços del tamany més chicotet possible. El número de cobertura de vèrtiços $τ$ és el tamany d'una cobertura mínima de vèrtiços, és dir, $τ = | V^{'} |$ . La figura inferior mostra eixemples de cobertura mínimes de vèrtiços en els grafos anteriors.

Eixemples

El conjunt de tots els vèrtiços és una cobertura de vèrtiços.
Els extrems de qualsevol emparellat màxim formen una cobertura de vèrtiços.
El grafo bipartito complet $K_{m, n}$ té una cobertura de vèrtiços mínima de tamany $τ (K_{m, n}) = \min {m, n}$ .

Propietats

Un conjunt de vèrtiços és una cobertura de vèrtiços si i solament si el seu complement és un conjunt independent.
En conseqüència, el número de vèrtiços d'un grafo és igual al seu número mínim de cobertura de vèrtiços més el tamany d'un conjunt màxim independent.^[1]

Problema computacional

El problema de cobertura mínima de vèrtiços és el problema d'optimisació de trobar la cobertura de vèrtiços més chicoteta en un grafo donat.

INSTANCIA: Grafo

G

SALIDA: Número menor

k

tal que

G

tinga una cobertura de vèrtiços de tamany

k

.

Si el problema es planteja com un problema de decisió, es denomina problema de cobertura de vèrtiços:

INSTANCIA: Siguen un grafo

G

i un sancer positiu

k

.

PREGUNTA: ¿Té

G

una cobertura de vèrtiços de tamany com a màxim

k

?

El problema de cobertura de vèrtiços és un problema NP-complet: era un de vintiun problemes NP-complets de Karp. S'utilisa a sovint en teoria de la complexitat computacional com a punt de partida per a les demostracions de NP-dificultat.

Formulació ILP

Suponga's que cada vèrtiç té un cost associat de $c (v) \geq 0$ . El problema de cobertura de vèrtiços mínim (ponderat) es pot formular com el següent cas de programació llineal en sancers (ILP).^[2]

Minimisar	$\sum_{v \in V} c (v) x_{v}$		(minimisar el cost total)
considerant	$x_{u} + x_{v} \geq 1$	para tot ${u, v} \in E$	(cobrix cada aresta del grafo),
	$x_{v} \in {0, 1}$	para tot $v \in V$ .	(cada vèrtiç està en la coberta de vèrtiços o no)

Este ILP pertany a la classe més general de ILPs para problemes de recobriment. El bot d'integritat d'este ILP és $2$ , per lo que la seua relaixació (permetent que cada variable estiga en l'interval de 0 a 1, en lloc de requerir que les variables siguen solament 0 o 1) dona un algoritme d'aproximació de factor $2$ per al problema de cobertura mínima de vèrtiços. Ademés, la relaixació de programació llineal d'eixe ILP és semientera; és dir, existix una solució òptima per a la qual cada entrada $x_{v}$ és 0, 1/2 o 1. Es pot obtindre una cobertura de vèrtiços aproximada a 2 a partir d'esta solució fraccionaria seleccionant el subconjunt de vèrtiços que les seues variables són distintes de zero.

Evaluació exacta

La variant de decisió del problema de cobertura de vèrtiços és NP-completa, lo que significa que és improvable que existixca un algoritme eficient per a resoldre-ho en exactitut per a grafos arbitraris. La NP-completitud es pot demostrar per mig de reducció a partir de la 3-satisfacibilidad o, com va fer Karp, per mig de reducció a partir del problema del clique. La cobertura de vèrtiços permaneix NP-completa inclús en grafos cúbics^[3] i inclús en grafos plans de grau 3 com a màxim.^[4]

Para grafos bipartitos, l'equivalència entre la cobertura de vèrtiços i la coincidència màxima descrita pel teorema de Kőnig permet resoldre el problema de cobertura de vèrtiços bipartita en temps polinòmic.

Para grafos en arbre, un algoritme troba una cobertura de vèrtiços mínima en temps polinòmic. Per a això, troba el primer full de l'arbre i afig el seu pare a la cobertura de vèrtiços mínima. Posteriorment, elimina el full, el pare i totes les arestes associades, i continua repetidament fins que no queden arestes en l'arbre.

Tratabilidad en paràmetros fixos

Un algoritme de busca exhaustiva pot resoldre el problema en un temps 2^kn^O(1), a on k és el tamany de la cobertura de vèrtiços. Per lo tant, la cobertura de vèrtiços és tractable en paràmetros fixos, i si solament interessen els valors menuts de k, es pot resoldre el problema en temps polinòmic. Una tècnica algorítmica que funciona ací es denomina algoritme d'arbre de busca acotat, i la seua idea és elegir repetidament un vèrtiç i ramificarlo recursivament, en dos casos en cada pas: colocar el vèrtiç actual o tots els seus veïns en la cobertura de vèrtiços.

L'algoritme per a resoldre la cobertura de vèrtiços que conseguix la millor dependència asintòtica del paràmetro s'eixecuta en el temps $O (1.273 8^{k} + (k \cdot n))$ .^[5] El valor klam d'este llímit de temps (una estimació del valor màxim del paràmetro que podria resoldre's en un temps raonable) és aproximadament 190. És dir, a menos que es troben millores algorítmiques adicionals, este algoritme solament és adequat per a casos el número dels quals de cobertura de vèrtiços siga 190 o inferior. Baix supòsits raonables de teoria de la complexitat, concretament per a la hipòtesis de temps exponencial, el temps d'eixecució no pot millorar-se a 2^o(k), inclús quan $n$ és $O (k)$ .

No obstant, para grafos plans, i de forma més general, per a grafos que exclouen algun grafo fix com a menor, es pot trobar una cobertura de vèrtiços de tamany k en el temps $2^{O (\sqrt{k})} n^{O (1)}$ , és dir, el problema és manejable en paràmetros fixos subexponencial.^[6] Este algoritme és, de nou, òptim, en el sentit de que, baix l'hipòtesis de temps exponencial, cap algoritme pot resoldre la cobertura de vèrtiços en grafos plans en el temps $2^{o (\sqrt{k})} n^{O (1)}$ .^[7]

Evaluació aproximada

Es pot trobar una aproximació de factor 2 prenent repetidament abdós extrems d'una aresta en la cobertura de vèrtiços i després eliminant-los del grafo. Dit d'un atre modo, es determina un emparellat M en un algoritme voraç i es construïx una cobertura de vèrtiços C que consta de tots els extrems de les arestes en M. En la següent figura, una coincidència màxima M està marcada en roig, i la cobertura de vèrtiços C està marcada en blau.

El conjunt C construït d'esta manera és una cobertura de vèrtiços: suponga's que una aresta i no està coberta per C; llavors M ∪ i és una coincidència i i ∉ M, la qual cosa contradiu la suposició de que M és màxima. Ademés, si i = o, v ∈ M, llavors qualsevol cobertura de vèrtiços, inclosa una cobertura de vèrtiços òptima, deu contindre o o v (o abdós). De lo contrari, l'aresta i no estaria coberta. És dir, una cobertura òptima conté a lo manco un extrem de cada aresta en M, i en total, el conjunt C és com a màxim dos voltes major que la cobertura òptima de vèrtiços.

Este senzill algoritme va ser descobert independentment per Fanica Gavril i Mihalis Yannakakis.^[8]

Tècniques més complexes mostren que existixen algoritmes d'aproximació en un factor d'aproximació llaugerament millor. Per eixemple, es coneix un algoritme d'aproximació en un factor d'aproximació de $2 - Θ (1 / \sqrt{\log | V |})$ .^[9] El problema es pot aproximar en un factor d'aproximació $2 / (1 + δ)$ en grafos $δ$ densos.^[10]

Inaproximabilidad

No es coneix un algoritme d'aproximació de factor constant millor que l'anterior. El problema de cobertura mínima de vèrtiços és APX-complet; és dir, no es pot aproximar arbitrariamente ben a menos que P = NP. Utilisant tècniques del teorema PCP, Dinur i Safra varen demostrar en 2005 que la cobertura mínima de vèrtiços no pot aproximar-se en un factor d'1,3606 per a cap grau de vèrtiç suficientment gran, a menos que P=NP.^[11] Posteriorment, el factor es va millorar a $\sqrt{2} - ϵ$ per a qualsevol $ϵ > 0$ .^[12]

Ademés, si la conjectura del joc únic és verdadera, la cobertura mínima de vèrtiços no pot aproximar-se en cap factor constant millor que 2.^[13]

Encara que trobar la cobertura mínima de vèrtiços és equivalent a trobar el conjunt independent de tamany màxim, com es va descriure anteriorment, abdós problemes no són equivalents sobre la preservació de l'aproximació: el problema del conjunt independent no té aproximació en factor constant a menos que P=NP.

Pseudocódigo

Algoritme d'aproximació:^[14]^[15]

APROXIMACIÓN-VÉRTICE-COBERTURA(G)
C= ∅
I'= G.E

while I' ≠ ∅:
    siga (o, v) una aresta arbitrària d'I'
    C= C ∪ {o, v}
    eliminar d'I' cada aresta incident en o o v
return C

Vore també

Referències

↑ Gallai, 1959.
↑ Vazirani 2003, pàg. 121–122
↑ Garey, Johnson & Stockmeyer 1974
↑ Garey & Johnson 1977; Garey & Johnson 1979, pp. 190 and 195.
↑ Chen, Kanj & Xia 2006
↑ Demaine et al. 2005
↑ Flum y Grohe (2006, p. 437)
↑ Papadimitriou & Steiglitz 1998, p. 432, mentions both Gavril and Yannakakis. Garey & Johnson 1979, p. 134, cites Gavril.
↑ Karakostas 2009
↑ Karpinski & Zelikovsky 1998
↑ Dinur & Safra 2005
↑ Khot, Minzer & Safra 2017; Dinur et al. Safra; Khot, Minzer & Safra 2018
↑ Khot & Regev 2008
↑ (2001 [1990]) «Section 35.1: The vertex-cover problem», Introduction to Algorithms, 2.ª edició, MIT Press and McGraw-Hill, pp. 1024–1027. ISBN 0-262-03293-7.
↑ «Approximation Algorithms: Vertex Cover». Computer Science 105. Dartmouth College. Consultat el 21 de febrer de 2005.

Bibliografia

A1.1: GT1, pág. 190.
Gallai, Tibor. “Über extreme Punkt- und Kantenmengen”. Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 2: 133–138.
Vazirani, Vijay V. (2003). Approximation Algorithms, Springer-Verlag. ISBN 978-3-662-04565-7.

Referències

Este artícul conté una traducció derivada de «Cobertura de vértices» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[FOOTNOTEGallai1959{{{c}}}-1] Gallai, 1959.

[2] Vazirani 2003, pàg. 121–122

[3] Garey, Johnson & Stockmeyer 1974

[4] Garey & Johnson 1977; Garey & Johnson 1979, pp. 190 and 195.

[5] Chen, Kanj & Xia 2006

[6] Demaine et al. 2005

[7] Flum y Grohe (2006, p. 437)

[8] Papadimitriou & Steiglitz 1998, p. 432, mentions both Gavril and Yannakakis. Garey & Johnson 1979, p. 134, cites Gavril.

[9] Karakostas 2009

[10] Karpinski & Zelikovsky 1998

[11] Dinur & Safra 2005

[12] Khot, Minzer & Safra 2017; Dinur et al. Safra; Khot, Minzer & Safra 2018

[kr08-13] Khot & Regev 2008

[14] (2001 [1990]) «Section 35.1: The vertex-cover problem», Introduction to Algorithms, 2.ª edició, MIT Press and McGraw-Hill, pp. 1024–1027. ISBN 0-262-03293-7.

[15] «Approximation Algorithms: Vertex Cover». Computer Science 105. Dartmouth College. Consultat el 21 de febrer de 2005.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]