En la disciplina matemática de la teoría de grafos , una cobertura de vértice (a veces cobertura de nodo ) de una gráfica es un conjunto de vértices que incluye al menos un punto final de cada borde de la gráfica . El problema de encontrar una cobertura mínima de vértices es un problema de optimización clásico en informática y es un ejemplo típico de un problema de optimización NP-hard que tiene un algoritmo de aproximación . Su versión de decisión , el problema de la cobertura del vértice , fue uno de los 21 problemas NP-completos de Karpy 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 es un problema central en la teoría de la complejidad parametrizada .
El problema de cobertura mínima de vértice se puede formular como un programa lineal semintegral cuyo programa lineal dual es el problema de coincidencia máxima .
Los problemas de cobertura de vértices se han generalizado a hipergráficos , consulte la cobertura de vértices en hipergráficos .
Definición
Formalmente, una cubierta de vértice de un gráfico no dirigido es un subconjunto de tal que , es decir es un conjunto de vértices donde cada borde tiene al menos un punto final en la cubierta del vértice . Se dice que tal conjunto cubre los bordes de. La figura superior muestra dos ejemplos de cubiertas de vértices, con algunas cubiertas de vértices. marcado en rojo.
Una cobertura de vértice mínima es una cobertura de vértice del tamaño más pequeño posible. El número de la cubierta del vértice es el tamaño de una cobertura de vértice mínima, es decir . La figura inferior muestra ejemplos de cubiertas de vértices mínimas en los gráficos anteriores.
Ejemplos de
- El conjunto de todos los vértices es una cobertura de vértices.
- Los puntos finales de cualquier coincidencia máxima forman una cobertura de vértice.
- El gráfico bipartito completo tiene una cobertura de vértice mínima de tamaño .
Propiedades
- Un conjunto de vértices es una cobertura de vértice si y solo si su complemento es un conjunto independiente .
- En consecuencia, el número de vértices de un gráfico es igual a su número mínimo de cobertura de vértice más el tamaño de un conjunto máximo independiente ( Gallai 1959).
Problema computacional
El problema de cobertura de vértice mínima es el problema de optimización de encontrar una cobertura de vértice más pequeña en un gráfico dado.
- INSTANCIA: Gráfico
- SALIDA: Número más pequeño tal que tiene una cubierta de vértice de tamaño .
Si el problema se establece como un problema de decisión , se denomina problema de cobertura de vértices :
- INSTANCIA: Gráfico y entero positivo .
- PREGUNTA: ¿Tiene tener una cubierta de vértice de tamaño como máximo ?
El problema de la cobertura de vértices es un problema NP-completo : era uno de los 21 problemas NP-completos de Karp . A menudo se utiliza en la teoría de la complejidad computacional como punto de partida para las pruebas de dureza NP .
Formulación de ILP
Suponga que cada vértice tiene un costo asociado de . El problema de cobertura mínima de vértices (ponderada) se puede formular como el siguiente programa lineal de enteros (ILP). [1]
minimizar (minimizar el costo total) sujeto a para todos (cubre todos los bordes del gráfico), para todos . (cada vértice está en la cubierta del vértice o no)
Este ILP pertenece a la clase más general de ILP para cubrir problemas . La brecha de integralidad de este ILP es, por lo que su relajación (permitiendo 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- 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 ILP es medio integral , es decir, existe una solución óptima para la cual cada entrada es 0, 1/2 o 1. Se puede obtener una cobertura de vértice aproximada de 2 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-completo , lo que significa que es poco probable que exista un algoritmo eficiente para resolverlo exactamente para gráficos arbitrarios. La completitud de NP puede demostrarse reduciendo la satisfacibilidad 3 o, como hizo Karp, reduciendo el problema de la camarilla . La cobertura de vértices permanece NP-completa incluso en gráficas cúbicas [2] e incluso en gráficas planas de grado como máximo 3. [3]
Para los gráficos bipartitos , la equivalencia entre la cobertura de vértices y la coincidencia máxima descrita por el teorema de Kőnig permite que el problema de cobertura de vértices bipartita se resuelva en tiempo polinomial .
Para los gráficos de árbol , un algoritmo encuentra una cobertura de vértice mínima en tiempo polinomial al encontrar la primera hoja en el árbol y agregar su padre a la cobertura de vértice mínima, luego eliminar la hoja y el padre y todos los bordes asociados y continuar repetidamente hasta que no queden bordes en el árbol.
Tratabilidad de parámetros fijos
Un algoritmo de búsqueda exhaustivo puede resolver el problema en el tiempo 2 k n O (1) , donde k es el tamaño de la cobertura del vértice. Por lo tanto, la cobertura de vértices es manejable con parámetros fijos , y si solo estamos interesados en k pequeños , podemos resolver el problema en tiempo polinomial . Una técnica algorítmica que funciona aquí se llama algoritmo de árbol de búsqueda acotado , y su idea es elegir repetidamente algún vértice y bifurcarse recursivamente, con dos casos en cada paso: colocar el vértice actual o todos sus vecinos en la cubierta del vértice. El algoritmo para resolver la cobertura de vértices que logra la mejor dependencia asintótica del parámetro se ejecuta en el tiempo.. [4] El valor klam de este límite de tiempo (una estimación del valor de parámetro más grande que podría resolverse en un período de tiempo razonable) 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értice es 190 o menos. Bajo supuestos razonables de la 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 cuando es .
Sin embargo, para gráficos planos , y más en general, para gráficos que excluyen algunos gráficos fijos como menor, se puede encontrar una cobertura de vértice de tamaño k en el tiempo, es decir, el problema es tratable subexponencialmente mediante parámetros fijos . [5] Este algoritmo es nuevamente óptimo, en el sentido de que, bajo la hipótesis del tiempo exponencial , ningún algoritmo puede resolver la cobertura de vértices en gráficas planas en el tiempo.. [6]
Evaluación aproximada
Se puede encontrar una aproximación de factor 2 tomando repetidamente ambos extremos de una arista en la cubierta del vértice y luego eliminándolos del gráfico. Dicho de otro modo, nos encontramos con una máxima coincidencia de M con un algoritmo codicioso y construimos una cubierta vértice C , que consiste en todos los puntos finales de los bordes en M . En la siguiente figura, una coincidencia máxima M está marcada con rojo y la cubierta del vértice C está marcada con azul.
El conjunto C construido de esta manera es una cubierta de vértice: suponga que una arista e no está cubierta por C ; entonces M ∪ { e } es una coincidencia y e ∉ M , lo cual es una contradicción con el supuesto de que M es máximo. Además, si e = { u , v } ∈ M , entonces cualquier cobertura de vértice, incluida una cobertura de vértice óptima, debe contener u o v (o ambos); de lo contrario, el borde e no está cubierto. Es decir, una cobertura óptima contiene al menos un punto final de cada borde en M ; en total, el conjunto C es como máximo 2 veces más grande que la cobertura de vértice óptima.
Este sencillo algoritmo fue descubierto de forma independiente por Fanica Gavril y Mihalis Yannakakis . [7]
Las técnicas más complicadas muestran 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 dees conocida. [8] El problema se puede aproximar con un factor de aproximación en - gráficos densos. [9]
Inaproximabilidad
No se conoce un 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 . [10] Más tarde, el factor se mejoró para para cualquier . [11] [12] Además, si la conjetura de los juegos únicos es cierta, la cobertura mínima de vértices no se puede aproximar 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 en una forma de preservación de la aproximación: El problema de conjuntos independientes no tiene una aproximación de factor constante a menos que P = NP .
Pseudocódigo
APROXIMACIÓN - VERTEX - COVER ( G ) = C = ∅ E ' = G . mimientras que E ' ≠ ∅ : dejar que ( u , v ) es una arbitraria borde de E ' C = C ∪ { u , v } de eliminación de E ' cada borde incidente en cualquiera de U o Vvolver C
[14] [15]
Aplicaciones
La optimización de la cobertura de vértices sirve como modelo para muchos problemas teóricos y del mundo real . Por ejemplo, un establecimiento comercial interesado en instalar la menor cantidad posible de cámaras de circuito cerrado que cubran todos los pasillos (bordes) que conectan todas las habitaciones (nodos) en un piso podría modelar el objetivo como un problema de minimización de cobertura de vértices. El problema también se ha utilizado para modelar la eliminación de secuencias repetitivas de ADN para aplicaciones de biología sintética e ingeniería metabólica . [16] [17]
Notas
- ^ Vazirani 2003 , págs. 121-122
- ^ Garey, Johnson y Stockmeyer 1974
- ^ Garey y Johnson 1977 ; Garey & Johnson 1979 , págs.190 y 195.
- ^ Chen, Kanj y Xia 2006
- ^ Demaine y col. 2005
- ^ Flum y Grohe (2006 , p. 437)
- ^ Papadimitriou y Steiglitz 1998 , p. 432, menciona tanto a Gavril como a Yannakakis. Garey y Johnson 1979 , pág. 134, cita a Gavril.
- ^ Karakostas 2009
- ^ Karpinski y Zelikovsky 1998
- ^ Dinur y Safra 2005
- ^ Khot, Minzer y Safra 2017se necesita cita completa ] [
- ^ Dinur y col. 2018se necesita cita completa ] [
- ^ Khot y Regev 2008
- ^ 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.
- ^ Chakrabarti, Amit (invierno de 2005). "Algoritmos de aproximación: cubierta de vértice" (PDF) . Ciencias de la Computación 105 . Universidad de Dartmouth . Consultado el 21 de febrero de 2005 .
- ^ Hossain, Ayaan; López, Eriberto; Halper, Sean M .; Cetnar, Daniel P .; Reis, Alexander C .; Strickland, Devin; Klavins, Eric; Salis, Howard M. (13 de julio de 2020). "Diseño automatizado de miles de piezas no repetitivas para la ingeniería de sistemas genéticos estables" . Biotecnología de la naturaleza . 38 (12): 1466–1475. doi : 10.1038 / s41587-020-0584-2 . ISSN 1087-0156 . PMID 32661437 . S2CID 220506228 .
- ^ Reis, Alexander C .; Halper, Sean M .; Vezeau, Grace E .; Cetnar, Daniel P .; Hossain, Ayaan; Clauer, Phillip R .; Salis, Howard M. (noviembre de 2019). "Represión simultánea de múltiples genes bacterianos utilizando matrices de sgRNA extralargas no repetitivas" . Biotecnología de la naturaleza . 37 (11): 1294-1301. doi : 10.1038 / s41587-019-0286-9 . ISSN 1546-1696 . PMID 31591552 . S2CID 203852115 .
Referencias
- Chen, Jianer; Kanj, Iyad A .; Xia, Ge (2006). "Límites superiores parametrizados mejorados para cobertura de vértice". Fundamentos matemáticos de la informática 2006: 31º Simposio Internacional, MFCS 2006, Stará Lesná, Eslovaquia, 28 de agosto al 1 de septiembre de 2006, Actas (PDF) . Apuntes de conferencias en informática. 4162 . Springer-Verlag. págs. 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, Mass .: 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-minor" . Revista de la ACM . 52 (6): 866–893. doi : 10.1145 / 1101821.1101823 . S2CID 6238832 . Consultado el 5 de marzo de 2010 .
- Dinur, Irit ; Safra, Samuel (2005). "Sobre la dureza de aproximar la cobertura mínima de vértice". 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 . Saltador. 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". Revista SIAM de Matemática Aplicada . 32 (4): 826–834. doi : 10.1137 / 0132071 .
- Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 0-7167-1045-5. A1.1: GT1, página 190.
- Garey, Michael R .; Johnson, David S .; Stockmeyer, Larry (1974). "Algunos problemas NP-completos simplificados" . Actas del Sexto Simposio Anual 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. Sci. Budapest, Secta Eötvös. Matemáticas . 2 : 133-138.
- Karakostas, George (noviembre de 2009). "Una mejor relación de aproximación para el problema de cobertura de vértices" (PDF) . Transacciones ACM sobre algoritmos . 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 Ubicación de Instalaciones . Serie DIMACS en Matemática Discreta e Informática Teórica. 40 . Sociedad Matemática Estadounidense. págs. 169-178.
- Khot, Subhash ; Regev, Oded (2008). "La cobertura del vértice puede ser difícil de aproximar dentro de 2 − ε". Revista de Ciencias de la Computación y Sistemas . 74 (3): 335–349. doi : 10.1016 / j.jcss.2007.06.019 .
- O'Callahan, Robert; Choi, Jong-Deok (2003). "Detección de carrera de datos dinámicos híbridos" . Actas del simposio ACM SIGPLAN sobre principios y práctica de la programación paralela (PPoPP 2003) y taller sobre evaluación parcial y manipulación de programas basada en semántica (PEPM 2003) . Avisos ACM SIGPLAN . 38 (10). págs. 167-178. doi : 10.1145 / 966049.781528 .
- 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.
enlaces externos
- Weisstein, Eric W. "Vertex Cover" . MathWorld .
- Weisstein, Eric W. "Cobertura mínima de vértice" . MathWorld .
- Weisstein, Eric W. "Número de portada de vértice" . MathWorld .
- Cruces de ríos (y números de Alcuin) - Numberphile