Cobertura de vértice

Subconjunto de los vértices de un gráfico, que incluye al menos un punto final de cada arista

Ejemplo de gráfico que tiene una cubierta 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 punto final de cada arista del grafo.

En informática , el problema de encontrar una cobertura mínima de vértices es un problema de optimización clásico . Es NP-hard , por lo que no se puede resolver mediante un algoritmo de tiempo polinomial si P ≠ NP . Además, es difícil de aproximar : no se puede aproximar hasta un factor menor que 2 si la conjetura de juegos únicos es verdadera. Por otro lado, tiene varias aproximaciones simples de 2 factores. 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 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 cobertura de vértices es manejable 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 semiintegral cuyo programa lineal dual es el problema de coincidencia máxima .

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

Definición

Ejemplos de coberturas de vértices

Ejemplos de coberturas mínimas de vértices

Formalmente, una cobertura de vértices de un grafo no dirigido es un subconjunto de tal que , es decir, es un conjunto de vértices donde cada arista tiene al menos un punto final en la cobertura de vértices . Se dice que un conjunto de este tipo cubre las aristas de . La figura superior muestra dos ejemplos de coberturas de vértices, con algunas coberturas de vértices marcadas en rojo. ${\displaystyle V'}$ ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle uv\in E\Rightarrow u\in V'\lor v\in V'}$ ${\displaystyle V'}$ ${\displaystyle V'}$ ${\displaystyle G}$ ${\displaystyle V'}$

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

Ejemplos

• El conjunto de todos los vértices es una cubierta de vértices.
• Los puntos finales de cualquier coincidencia máxima forman una cubierta de vértices.
• El gráfico bipartito completo tiene una cobertura de vértices mínima de tamaño . ${\displaystyle K_{m,n}}$ ${\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}$

Propiedades

• Un conjunto de vértices es una cubierta de vértices si y sólo 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 cobertura mínima de vértices es el problema de optimización que consiste en encontrar la cobertura mínima de vértices en un gráfico dado.

INSTANCIA: Gráfico ${\displaystyle G}$

SALIDA: Número más pequeño tal que tiene una cubierta de vértice de tamaño . ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$

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

INSTANCIA: Gráfica y entero positivo . ${\displaystyle G}$ ${\displaystyle k}$

PREGUNTA: ¿ Tiene una cubierta de vértice de tamaño como máximo ? ${\displaystyle G}$ ${\displaystyle k}$

El problema de la cobertura de vértices es un problema NP-completo : fue uno de los 21 problemas NP-completos de Karp . Se utiliza a menudo en la teoría de la complejidad computacional como punto de partida para las pruebas de NP-dureza .

Formulación de ILP

Supongamos que cada vértice tiene un costo asociado de . El problema de cobertura mínima de vértices (ponderado) se puede formular como el siguiente programa lineal entero (ILP). ^[2] ${\displaystyle c(v)\geq 0}$

Este ILP pertenece a la clase más general de ILP para problemas de cobertura . 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) proporciona un algoritmo de aproximación de factores para el problema de cobertura mínima de vértices. Además, la relajación de programación lineal de ese ILP es semientera , es decir, existe una solución óptima para la que cada entrada es 0, 1/2 o 1. Se puede obtener una cobertura de vértices aproximada a 2 a partir de esta solución fraccionaria seleccionando el subconjunto de vértices cuyas variables no son cero. ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle x_{v}}$

Evaluación exacta

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

Para gráficos bipartitos , la equivalencia entre la cobertura de vértices y la correspondencia máxima descrita por el teorema de König permite resolver el problema de cobertura de vértices bipartitos en tiempo polinomial .

Para los gráficos de árboles , un algoritmo encuentra una cobertura de vértice mínima en tiempo polinomial encontrando la primera hoja en el árbol y agregando su padre a la cobertura de vértice mínima, luego eliminando la hoja y el padre y todos los bordes asociados y continuando repetidamente hasta que no queden bordes 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 manejable con parámetros fijos y, si solo nos interesan 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 ramificarse 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 tiempo . ^[5] 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 una cantidad 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értices sea 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 cuando es . ${\displaystyle O(1.2738^{k}+(k\cdot n))}$ ${\displaystyle n}$ ${\displaystyle O(k)}$

Sin embargo, para los grafos planares , y más generalmente, para los grafos que excluyen algún grafo fijo como menor, se puede encontrar una cobertura de vértices de tamaño k en el tiempo , es decir, el problema es manejable con parámetros fijos de manera subexponencial . ^[6] 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 grafos planares en el tiempo . ^[7] ${\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}$ ${\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}$

Evaluación aproximada

Se puede encontrar una aproximación de factor 2 tomando repetidamente ambos puntos finales de una arista en la cubierta de vértices y luego quitándolos del gráfico. Dicho de otro modo, encontramos una coincidencia máxima M con un algoritmo voraz y construimos una cubierta de vértices C que consta de todos los puntos finales de las aristas en M. En la siguiente figura, una coincidencia máxima M está marcada en rojo y la cubierta 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 una coincidencia y e  ∉  M , lo cual es una contradicción con el supuesto de que M es maximal. Además, si e  = { u ,  v } ∈ M , entonces cualquier cobertura de vértices –incluyendo una cobertura de vértices óptima– debe contener u o v (o ambas); de lo contrario, la arista e no está cubierta. Es decir, una cobertura óptima contiene al menos un punto final 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 algoritmo simple fue descubierto independientemente por Fanica Gavril y Mihalis Yannakakis . ^[8]

Las técnicas más complejas muestran que existen algoritmos de aproximación con un factor de aproximación ligeramente mejor. Por ejemplo, se conoce un algoritmo de aproximación con un factor de aproximación de. ^[9] El problema se puede aproximar con un factor de aproximación en grafos densos. ^[10] ${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$ ${\displaystyle 2/(1+\delta )}$ ${\displaystyle \delta }$

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 . ^[11] Más tarde, el factor se mejoró a para cualquier . ^[12] Además, si la conjetura de juegos únicos es verdadera, entonces la cobertura mínima de vértices no se puede aproximar dentro de ningún factor constante mejor que 2. ^[13] ${\displaystyle {\sqrt {2}}-\epsilon }$ ${\displaystyle \epsilon >0}$

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 un sentido de preservación de la aproximación: el problema del conjunto independiente no tiene una aproximación de factor constante a menos que P  =  NP .

Pseudocódigo

APROXIMACIÓN - VÉRTICE - COBERTURA ( G ) C = ∅ E ' = G . E   mientras E ' ≠ ∅ : sea ( u , v ) una arista arbitraria de E ' C = C ∪ { u , v } elimine de E ' cada arista incidente en u o v​​                             devolver 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) de un piso podría modelar el objetivo como un problema de minimización de la 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]}

Véase también

• Conjunto dominante

Notas

1. Galla 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 y otros, 2005
7. Flum y Grohe (2006, pág. 437)
8. Papadimitriou y Steiglitz 1998, pág. 432, mencionan tanto a Gavril como a Yannakakis. Garey y Johnson 1979, pág. 134, citan 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 de 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 .
16. Hossain, Ayaan; Lopez, 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 partes no repetitivas para la ingeniería de sistemas genéticos estables". Nature Biotechnology . 38 (12): 1466–1475. doi :10.1038/s41587-020-0584-2. ISSN  1087-0156. PMID  32661437. S2CID  220506228.
17. 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". Nature Biotechnology . 37 (11): 1294–1301. doi :10.1038/s41587-019-0286-9. ISSN  1546-1696. OSTI  1569832. PMID  31591552. S2CID  203852115.

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) . Apuntes de clase en informática. Vol. 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 subexponenciales parametrizados en grafos de género acotado y grafos libres de H-menores". Journal of the 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 prueba 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. págs. 376–389. doi :10.1145/3188745.3188804. ISBN 978-1-4503-5559-9.CECC TR16-198  .
• Dinur, Irit ; Safra, Samuel (2005). "Sobre la dificultad de aproximar la cobertura mínima de vértices". Anales de Matemáticas . 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". Revista SIAM de Matemáticas Aplicadas . 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 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 relació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 ubicación de instalaciones . Serie DIMACS en matemáticas discretas y ciencias de la computación 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. págs. 576–589. doi :10.1145/3055399.3055432. ISBN. 978-1-4503-4528-6.CECC TR16-124  .
• Khot, Subhash ; Minzer, Dor; Safra, Muli (2018). "Los conjuntos pseudoaleatorios en el gráfico de Grassmann tienen una expansión casi perfecta". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . págs. 592–601. doi :10.1109/FOCS.2018.00062. ISBN 978-1-5386-4230-6. Número de identificación del sujeto  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.

Enlaces externos

• Weisstein, Eric W. "Cobertura de vértice". MathWorld .
• Weisstein, Eric W. "Cobertura mínima de vértices". MathWorld .
• Weisstein, Eric W. "Número de cubierta de vértice". MathWorld .
• Cruces de ríos (y números de Alcuino) – Numberphile