Cobertura de vértice

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 .

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. ${\estilo de visualización 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'|}$

• 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\,\}}$

• 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]

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 .

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}}$

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.

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)}}$

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 }$

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 .

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]}

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]}

• Conjunto dominante

• 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