Hispanopedia Wiki
Articulo de referencia

cobertura de vértices

Ejemplo de grafo que tiene una cobertura de vértices que comprende 2 vértices (abajo), pero ninguno con menos En teoría de grafos , una cobertura de vértices (a veces cobertura ...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo de grafo que tiene una cobertura de vértices que comprende 2 vértices (abajo), pero ninguno con menos

En teoría de grafos , una cobertura de vértices (a veces cobertura de nodos ) de un grafo es un conjunto de vértices que incluye al menos un extremo de cada arista del grafo.

En ciencias de la computación , el problema de encontrar una cobertura de vértices mínima es un problema de optimización clásico . Es NP-difícil , por lo que no puede resolverse mediante un algoritmo de tiempo polinomial si P ≠ NP . Además, es difícil de aproximar : no puede aproximarse hasta un factor menor que 2 si la conjetura de juegos únicos es cierta. Por otro lado, tiene varias aproximaciones simples de factor 2. Es un ejemplo típico de un problema de optimización NP-difícil que tiene un algoritmo de aproximación . Su versión de decisión , el problema de la cobertura de vértices , fue uno de los 21 problemas NP-completos de Karp y, por lo tanto, es un problema NP-completo clásico en la teoría de la complejidad computacional . Además, el problema de la cobertura de vértices es tratable con parámetros fijos y un problema central en la teoría de la complejidad parametrizada .

El problema de cobertura mínima de vértices se puede formular como un programa lineal semi -entero cuyo programa lineal dual es el problema de emparejamiento máximo .

Los problemas de cobertura de vértices se han generalizado a hipergrafos , véase Cobertura de vértices en hipergrafos .

Definición

Ejemplos de recubrimientos de vértices
Ejemplos de coberturas de vértices mínimas

Formalmente, una cubierta de vérticesV′{\displaystyle V'}de un grafo no dirigidoGRAMO=(V,mi){\displaystyle G=(V,E)}es un subconjunto deV{\displaystyle V}de tal manera que(túv∈mi)⇒(tú∈V′∨v∈V′){\displaystyle (uv\in E)\Rightarrow (u\in V'\lor v\in V')}, es decir, es un conjunto de vérticesV′{\displaystyle V'}donde cada arista tiene al menos un extremo en la cobertura de vértices.V′{\displaystyle V'}Se dice que tal conjunto cubre los bordes deGRAMO{\displaystyle G}La figura superior muestra dos ejemplos de cubiertas de vértices, con alguna cubierta de vérticesV′{\displaystyle V'}marcado en rojo.

Una cobertura de vértices mínima es una cobertura de vértices del tamaño más pequeño posible. El número de cobertura de vérticesτ{\displaystyle \tau }es el tamaño de una cobertura de vértices mínima, es decirτ=|V′|{\displaystyle \tau =|V'|}La figura inferior muestra ejemplos de coberturas mínimas de vértices en los gráficos anteriores.

Ejemplos

  • El conjunto de todos los vértices es una cubierta de vértices.
  • Los extremos de cualquier emparejamiento máximo forman una cobertura de vértices.
  • El grafo bipartito completoKmetro,norte{\displaystyle K_{m,n}}tiene una cobertura de vértice mínima de tamañoτ(Kmetro,norte)=min{metro,norte}{\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}.

Propiedades

  • Un conjunto de vértices es una cubierta de vértices si y solo si su complemento es un conjunto independiente .
  • En consecuencia, el número de vértices de un grafo es igual a su número mínimo de cobertura de vértices más el tamaño de un conjunto independiente máximo. [ 1 ]

Problema computacional

El problema de la cobertura mínima de vértices es el problema de optimización que consiste en encontrar la cobertura de vértices más pequeña en un grafo dado.

INSTANCIA: GrafoGRAMO{\displaystyle G}
SALIDA: Número más pequeñok{\displaystyle k}de tal manera queGRAMO{\displaystyle G}tiene una cubierta de vértices de tamañok{\displaystyle k}.

Si el problema se plantea como un problema de decisión , se denomina problema de cobertura de vértices :

INSTANCIA: GrafoGRAMO{\displaystyle G}y entero positivok{\displaystyle k}.
PREGUNTA: ¿EsGRAMO{\displaystyle G}tener una cubierta de vértices de tamaño como máximok{\displaystyle k}¿

Son equivalentes bajo la reducción en tiempo polinomial mediante búsqueda binaria . El problema de cobertura de vértices es un problema NP-completo : fue uno de los 21 problemas NP-completos de Karp . Se utiliza frecuentemente en la teoría de la complejidad computacional como punto de partida para demostraciones de NP-dureza .

Formulación ILP

Supongamos que cada vértice tiene un costo asociado dedo(v)≥0{\displaystyle c(v)\geq 0}El problema de cobertura mínima de vértices (ponderada) puede formularse como el siguiente programa lineal entero (PLI). [ 2 ]

Este ILP pertenece a la clase más general de ILP para problemas de cobertura . La brecha de integralidad de este ILP es2{\displaystyle 2}, por lo que su relajación (que permite que cada variable esté en el intervalo de 0 a 1, en lugar de requerir que las variables sean solo 0 o 1) da un factor-2{\displaystyle 2}algoritmo de aproximación para el problema de cobertura mínima de vértices. Además, la relajación de programación lineal de ese PIL es semi-entero , es decir, existe una solución óptima para la cual cada entradaincógnitav{\displaystyle x_{v}}es 0, 1/2 o 1. Se puede obtener una cobertura de vértices 2-aproximada a partir de esta solución fraccionaria seleccionando el subconjunto de vértices cuyas variables son distintas de cero.

Evaluación exacta

La variante de decisión del problema de cobertura de vértices es NP-completa , lo que significa que es improbable que exista un algoritmo eficiente para resolverla exactamente en grafos arbitrarios. La NP-completitud se puede demostrar mediante reducción a partir de la 3-satisfacibilidad o, como hizo Karp, mediante reducción a partir del problema de clique . La cobertura de vértices sigue siendo NP-completa incluso en grafos cúbicos [ 3 ] e incluso en grafos planares de grado como máximo 3 [ 4 ].

Para grafos bipartitos , la equivalencia entre cobertura de vértices y emparejamiento máximo descrita por el teorema de Kőnig permite resolver el problema de cobertura de vértices bipartitos en tiempo polinomial .

Para los grafos de árbol , un algoritmo encuentra una cobertura mínima de vértices en tiempo polinomial al encontrar la primera hoja del árbol y agregar su padre a la cobertura mínima de vértices, luego eliminar la hoja y el padre y todas las aristas asociadas y continuar repetidamente hasta que no queden aristas en el árbol.

Tratabilidad de parámetros fijos

Un algoritmo de búsqueda exhaustiva puede resolver el problema en tiempo 2 k n O (1) , donde k es el tamaño de la cobertura de vértices. Por lo tanto, la cobertura de vértices es tratable con parámetros fijos , y si solo nos interesan valores pequeños de k , podemos resolver el problema en tiempo polinomial . Una técnica algorítmica que funciona aquí se llama algoritmo de árbol de búsqueda acotada , y su idea es elegir repetidamente algún vértice y ramificar recursivamente, con dos casos en cada paso: colocar el vértice actual o todos sus vecinos en la cobertura de vértices. El algoritmo para resolver la cobertura de vértices que logra la mejor dependencia asintótica del parámetro se ejecuta en tiempoO(1.2738k+(k⋅norte)){\displaystyle O(1.2738^{k}+(k\cdot n))}. [ 5 ] El valor klam de este límite de tiempo (una estimación para el valor de parámetro más grande que podría resolverse en una cantidad razonable de tiempo) es aproximadamente 190. Es decir, a menos que se puedan encontrar mejoras algorítmicas adicionales, este algoritmo es adecuado solo para instancias cuyo número de cobertura de vértices es 190 o menos. Bajo supuestos razonables de teoría de la complejidad, a saber, la hipótesis del tiempo exponencial , el tiempo de ejecución no se puede mejorar a 2 o ( k ) , incluso cuandonorte{\displaystyle n}esO(k){\displaystyle O(k)}.

Sin embargo, para grafos planares , y más generalmente, para grafos que excluyen algún grafo fijo como menor, se puede encontrar una cobertura de vértices de tamaño k en tiempo2O(k)norteO(1){\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}, es decir, el problema es subexponencialmente tratable con parámetros fijos . [ 6 ] Este algoritmo es nuevamente óptimo, en el sentido de que, bajo la hipótesis de tiempo exponencial , ningún algoritmo puede resolver la cobertura de vértices en grafos planares en tiempo2o(k)norteO(1){\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}. [ 7 ]

Evaluación aproximada

Se puede obtener una aproximación de factor 2 tomando repetidamente ambos extremos de una arista en la cobertura de vértices y luego eliminándolos del grafo. Dicho de otro modo, encontramos un emparejamiento máximo M con un algoritmo voraz y construimos una cobertura de vértices C que consta de todos los extremos de las aristas en M. En la siguiente figura, el emparejamiento máximo M está marcado en rojo y la cobertura de vértices C está marcada en azul.

El conjunto C construido de esta manera es una cobertura de vértices: supongamos que una arista e no está cubierta por C ; entonces M  ∪  { e } es un emparejamiento y e  ∉ M , lo cual contradice la suposición de que M es maximal. Además, si e = { u , v } ∈ M , entonces cualquier cobertura de vértices —incluida una cobertura de vértices óptima— debe contener u o v (o ambos); de lo contrario, la arista e no está cubierta. Es decir, una cobertura óptima contiene al menos un extremo de cada arista en M ; en total, el conjunto C es como máximo 2 veces más grande que la cobertura de vértices óptima.    

Este sencillo algoritmo fue descubierto independientemente por Fanica Gavril y Mihalis Yannakakis . [ 8 ]

Técnicas más complejas demuestran que existen algoritmos de aproximación con un factor de aproximación ligeramente mejor. Por ejemplo, un algoritmo de aproximación con un factor de aproximación de2−Θ(1/registro⁡|V|){\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}es conocido. [ 9 ] El problema puede aproximarse con un factor de aproximación2/(1+δ){\displaystyle 2/(1+\delta )}enδ{\displaystyle \delta }- grafos densos. [ 10 ]

Inaproximabilidad

No se conoce ningún algoritmo de aproximación de factor constante mejor que el anterior. El problema de cobertura mínima de vértices es APX-completo , es decir, no se puede aproximar arbitrariamente bien a menos que P  = NP  . Utilizando técnicas del teorema PCP , Dinur y Safra demostraron en 2005 que la cobertura mínima de vértices no se puede aproximar dentro de un factor de 1,3606 para cualquier grado de vértice suficientemente grande a menos que P  = NP . [ 11 ] Posteriormente, el factor se mejoró a 2−ϵ{\displaystyle {\sqrt {2}}-\epsilon }para cualquierϵ>0{\displaystyle \epsilon >0}. [ 12 ] Además, si la conjetura de juegos únicos es cierta, entonces la cobertura mínima de vértices no puede aproximarse dentro de ningún factor constante mejor que 2. [ 13 ]

Aunque encontrar la cobertura de vértices de tamaño mínimo es equivalente a encontrar el conjunto independiente de tamaño máximo, como se describió anteriormente, los dos problemas no son equivalentes de una manera que preserve la aproximación: el problema del conjunto independiente no tiene una aproximación de factor constante a menos que P  = NP . 

Pseudocódigo

Algoritmo de aproximación: [ 14 ] [ 15 ]

APROXIMACIÓN - VÉRTICE - CUBIERTA ( G ) C = ∅ E ' = G . EMientras E ' ≠ ∅ : sea ( u , v ) una arista arbitraria de E ' C = C ∪ { u , v } elimine de E ' toda arista incidente en u o v​​devolver C

Véase también

Notas

  1. ↑ Gallai 1959 .
  2. ^ Vazirani 2003 , págs. 121-122 
  3. ^ Garey, Johnson y Stockmeyer 1974
  4. ^ Garey y Johnson 1977 ; Garey y Johnson 1979 , págs. 190 y 195.
  5. ^ Chen, Kanj y Xia 2006
  6. ↑ Demaine et al. 2005
  7. ↑ Flum y Grohe (2006 , pág. 437) 
  8. ↑ Papadimitriou y Steiglitz 1998 , pág. 432, menciona tanto a Gavril como a Yannakakis. Garey y Johnson 1979 , pág. 134, cita a Gavril.
  9. ↑ Karakostas 2009
  10. ↑ Karpinski y Zelikovsky 1998
  11. ↑ Dinur y Safra 2005
  12. ^ Khot, Minzer y Safra 2017 ; Dinur et al. 2018 ; Khot, Minzer y Safra 2018
  13. ↑ Khot y Regev 2008
  14. ↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "Sección 35.1: El problema de la cobertura de vértices". Introducción a los algoritmos (2.ª  ed.). MIT Press y McGraw-Hill. págs. 1024–1027 . ISBN  0-262-03293-7.
  15. ↑ Chakrabarti, Amit (Invierno 2005). "Algoritmos de aproximación: cobertura de vértices" (PDF) . Ciencias de la Computación 105. Dartmouth College . Consultado el 21 de febrero de 2005 .

Referencias

  • Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). "Límites superiores parametrizados mejorados para la cobertura de vértices". Fundamentos matemáticos de la informática 2006: 31.º Simposio Internacional, MFCS 2006, Stará Lesná, Eslovaquia, 28 de agosto - 1 de septiembre de 2006, Actas (PDF) . Lecture Notes in Computer Science. Vol.  4162. Springer-Verlag. pp. 238–249 . doi : 10.1007/11821069_21 . ISBN  978-3-540-37791-7.
  • Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Introducción a los algoritmos . Cambridge, Massachusetts: MIT Press y McGraw-Hill. págs. 1024 –1027. ISBN  0-262-03293-7.
  • Demaine, Erik ; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2005). "Algoritmos parametrizados subexponenciales en gráficos de género acotado y gráficos libres de H menor" . Revista de la ACM . 52 (6): 866– 893. doi : 10.1145/1101821.1101823 . S2CID 6238832 . Consultado el 5 de marzo de 2010 . 
  • Dinur, Irit ; Khot, Subhash ; Kindler, Guy; Minzer, Dor; Safra, Muli (2018). "¿Hacia una demostración de la conjetura de los juegos 2 a 1?". En Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.). Actas del 50.º Simposio Anual ACM SIGACT sobre Teoría de la Computación, STOC 2018, Los Ángeles, CA, EE. UU., 25-29 de junio de 2018. Association for Computing Machinery. pp. 376–389 . doi : 10.1145/3188745.3188804 . ISBN  978-1-4503-5559-9. ECCC TR16-198 . 
  • Dinur, Irit ; Safra, Samuel (2005). "Sobre la dificultad de aproximar la cobertura mínima de vértices". Annals of Mathematics . 162 (1): 439– 485. CiteSeerX 10.1.1.125.334 . doi : 10.4007/annals.2005.162.439 . 
  • Flum, Jörg; Grohe, Martin (2006). Teoría de la complejidad parametrizada . Springer. doi : 10.1007/3-540-29953-X . ISBN 978-3-540-29952-3. Consultado el 5 de marzo de 2010 .
  • Garey, Michael R. ; Johnson, David S. (1977). "El problema del árbol de Steiner rectilíneo es NP-completo". SIAM Journal on Applied Mathematics . 32 (4): 826– 834. doi : 10.1137/0132071 .
  • Garey, Michael R.; Johnson , David S. (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . WH Freeman. ISBN 0-7167-1045-5.A1.1: GT1, pág. 190.
  • Garey, Michael R.; Johnson , David S .; Stockmeyer, Larry (1974). "Algunos problemas NP-completos simplificados" . Actas del Sexto Simposio Anual de la ACM sobre Teoría de la Computación . págs. 47–63 . doi : 10.1145/800119.803884 . 
  • Gallai, Tibor (1959). "Über extreme Punkt- und Kantenmengen". Ana. Univ. Ciencia. Budapest, secta Eötvös. Matemáticas . 2 : 133-138 .
  • Karakostas, George (noviembre de 2009). "Una mejor razón de aproximación para el problema de cobertura de vértices" (PDF) . ACM Transactions on Algorithms . 5 (4): 41:1–41:8. CiteSeerX 10.1.1.649.7407 . doi : 10.1145/1597036.1597045 . S2CID 2525818. ECCC TR04-084 .   
  • Karpinski, Marek; Zelikovsky, Alexander (1998). "Aproximación de casos densos de problemas de cobertura" . Actas del Taller DIMACS sobre Diseño de Redes: Conectividad y Localización de Instalaciones . Serie DIMACS en Matemáticas Discretas e Informática Teórica. Vol.  40. Sociedad Matemática Americana. págs. 169–178 . 
  • Khot, Subhash ; Minzer, Dor; Safra, Muli (2017). «Sobre conjuntos independientes, juegos 2 a 2 y grafos de Grassmann». En Hatami, Hamed; McKenzie, Pierre; King, Valerie (eds.). Actas del 49.º Simposio Anual ACM SIGACT sobre Teoría de la Computación, STOC 2017, Montreal, QC, Canadá, 19-23 de junio de 2017. Association for Computing Machinery. pp. 576–589 . doi : 10.1145/3055399.3055432 . ISBN  978-1-4503-4528-6. ECCC TR16-124 . 
  • Khot, Subhash ; Minzer, Dor; Safra, Muli (2018). "Los conjuntos pseudoaleatorios en el grafo de Grassmann tienen una expansión casi perfecta". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . pp. 592–601 . doi : 10.1109/FOCS.2018.00062 . ISBN  978-1-5386-4230-6. S2CID 3688775 . 
  • Khot, Subhash ; Regev, Oded (2008). "La cobertura de vértices podría ser difícil de aproximar dentro de 2 − ε" . Journal of Computer and System Sciences . 74 (3): 335– 349. doi : 10.1016/j.jcss.2007.06.019 .
  • Papadimitriou, Christos H. ; Steiglitz, Kenneth (1998). Optimización combinatoria: algoritmos y complejidad . Dover.
  • Vazirani, Vijay V. (2003). Algoritmos de aproximación . Springer-Verlag. ISBN 978-3-662-04565-7.