Cubierta de vértice

Subconjunto de los vértices de un gráfico, incluido al menos un punto final de cada borde

Gráfico de ejemplo 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 gráfico es un conjunto de vértices que incluye al menos un punto final de cada borde del gráfico.

En informática , el problema de encontrar una cobertura mínima de vértices 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 se puede aproximar hasta un factor menor que 2 si la conjetura del juego único es cierta. 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 la cobertura de vértices es manejable 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értices se puede formular como un programa lineal semiintegral cuyo programa lineal dual es el problema de máxima coincidencia .

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

Definición

Ejemplos de cubiertas de vértices

Ejemplos de coberturas mínimas de vértices

Formalmente, una cobertura de vértices de un gráfico 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 los bordes 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 de vértice mínima 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 de vértice mínima, es decir . La figura inferior muestra ejemplos de coberturas mínimas de vértices 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 cobertura de vértice.
• El gráfico bipartito completo tiene una cobertura de vértice 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 cobertura de vértices si y sólo 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értices más el tamaño de un conjunto máximo independiente. ^[1]

problema computacional

El problema de cobertura mínima de vértice es el problema de optimización de encontrar la cobertura de vértice más pequeña en un gráfico determinado.

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

SALIDA: Número más pequeño que tiene una cobertura 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 cobertura 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 . A menudo se utiliza en la teoría de la complejidad computacional como punto de partida para las pruebas de dureza NP .

formulación ILP

Supongamos que cada vértice tiene un costo asociado de . El problema de cobertura de vértice mínimo (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 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 algoritmo de aproximación factorial para el problema de cobertura mínima de vértices. Además, la relajación de programación lineal de ese ILP es semiintegral , es decir, existe una solución óptima para la cual cada entrada es 0, 1/2 o 1. Se puede obtener una cobertura de 2 vértices aproximados a partir de esta solución fraccionaria. seleccionando el subconjunto de vértices cuyas variables son distintas de 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 gráficos arbitrarios. La completitud NP se puede demostrar mediante la reducción de la satisfacibilidad 3 o, como hizo Karp, mediante la reducción del problema de la camarilla . La cobertura de vértices sigue siendo NP completa incluso en gráficos cúbicos ^[3] e incluso en gráficos planos de grado 3 como máximo. ^[4]

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

Para los gráficos de árbol , un algoritmo encuentra una cobertura de vértice mínima en tiempo polinómico al encontrar la primera hoja del á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ño , 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 ramificar recursivamente, con dos casos en cada paso: colocar el vértice actual o todos sus vecinos en la cubierta 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 el 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 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 sólo para instancias cuyo número de cobertura de vértices es 190 o menos. Bajo supuestos razonables de la teoría de la complejidad, es decir, 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 gráficos planos , y más generalmente, para gráficos que excluyen algún gráfico fijo como menor, se puede encontrar en el tiempo una cobertura de vértice de tamaño k , es decir, el problema es manejable subexponencial de parámetros fijos . ^[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 gráficos planos 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 un borde en la cubierta del vértice y luego eliminándolos del gráfico. Dicho de otra manera, encontramos una coincidencia máxima M con un algoritmo codicioso y construimos una cubierta de vértice C que consta de todos los puntos finales de los bordes en M. En la siguiente figura, una coincidencia máxima M está marcada en rojo y la cubierta de vértice C está marcada en azul.

El conjunto C construido de esta manera es una cobertura de vértice: 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 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 queda cubierto. 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értice óptima.

Este sencillo algoritmo fue descubierto de forma independiente por Fanica Gavril y Mihalis Yannakakis . ^[8]

Técnicas más complicadas 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 gráficos densos. ^[10] ${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$ ${\displaystyle 2/(1+\delta )}$ ${\displaystyle \delta }$

Inaccesibilidad

No se conoce ningún algoritmo de aproximación de factor constante mejor que el anterior. El problema de cobertura mínima de vértice 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értice no puede aproximarse dentro de un factor de 1,3606 para ningún grado de vértice suficientemente grande a menos que P  =  NP . ^[11] Posteriormente, el factor se mejoró a para cualquier . ^[12] Además, si la conjetura de los 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] ${\displaystyle {\sqrt {2}}-\epsilon }$ ${\displaystyle \epsilon >0}$

Aunque encontrar la cobertura de vértice 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 del conjunto independiente no tiene aproximación de factor constante a menos que P  =  NP .

Pseudocódigo

APROXIMACIÓN - VÉRTEX - CUBIERTA ( G ) C = ∅ E ' = G . mi   mientras que E ' ≠ ∅ : sea ( u , v ) una arista arbitraria de E ' C = C ∪ { u , v } elimine de E ' cada arista incidente en u o v​                             regresar 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 la cobertura de vértices. El problema también se ha utilizado para modelar la eliminación de secuencias de ADN repetitivas para aplicaciones de biología sintética e ingeniería metabólica . ^{[16] [17]}

Ver también

• Conjunto dominante

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 y col. 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. Karakosta 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 . Universidad de Dartmouth . Consultado el 21 de febrero de 2005 .
16. Hossain, Ayaan; López, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alejandro 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.
17. Reis, Alejandro C.; Halper, Sean M.; Vézeau, 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. 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 al 1 de septiembre de 2006, Actas (PDF) . Apuntes de conferencias sobre 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, 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, chico; Minzer, Dor; Safra, Muli (2018). "¿Hacia una prueba de la conjetura de los juegos 2 a 1?". En Diaconikolas, 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 al 29 de junio de 2018 . Asociación para Maquinaria de Computación. págs. 376–389. doi :10.1145/3188745.3188804. ECCC  TR16-198.
• Dinur, Irit ; Safra, Samuel (2005). "Sobre la dureza 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, Martín (2006). Teoría de la Complejidad Parametrizada. Saltador. 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 rectilíneo de Steiner 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 la integridad NP . 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 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) . 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, Alejandro (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. vol. 40. Sociedad Matemática Estadounidense. págs. 169-178.
• Khot, Subhash ; Minzer, Dor; Safra, Muli (2017). "Sobre sets independientes, juegos 2 a 2 y gráficos de Grassmann". En Hatami, Hamed; McKenzie, Pedro; Rey, Valerie (eds.). Actas del 49.º Simposio anual ACM SIGACT sobre teoría de la computación, STOC 2017, Montreal, QC, Canadá, 19 al 23 de junio de 2017 . Asociación para Maquinaria de Computación. págs. 576–589. doi :10.1145/3055399.3055432. ECCC  TR16-124.
• Khot, Subhash ; Minzer, Dor; Safra, Muli (2018). "Los conjuntos pseudoaleatorios en el gráfico de Grassmann tienen una expansión casi perfecta". 59.º Simposio anual del IEEE de 2018 sobre fundamentos de la informática (FOCS) . págs. 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 puede ser difícil de aproximar dentro de 2 − ε". Revista de Ciencias de la Computación y de Sistemas . 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. "Cubierta de vértice". MundoMatemático .
• Weisstein, Eric W. "Cobertura mínima de vértice". MundoMatemático .
• Weisstein, Eric W. "Número de portada de Vertex". MundoMatemático .
• Cruces de ríos (y números de Alcuino) – Numberphile