Cobertura de vértices

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 mínima de vértices es un problema de optimización clásico. Es NP-difícil, por lo que no puede resolverse con un algoritmo de tiempo polinómico si P ≠ NP. Además, es difícil de aproximar: no puede aproximarse hasta un factor menor que 2 si la conjetura del juego único es verdadera. Por otro lado, tiene varias aproximaciones simples de 2 factores. 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 cobertura de vértices, fue uno de los veintiún problemas NP-completos de Karp y, por lo tanto, es un problema clásico NP-completo en 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 puede formularse como un caso de programación lineal semi entero, cuyo programa lineal dual es el problema de máxima coincidencia.

Los problemas de cobertura de vértices se han generalizado a los hipergrafos; véase cubiertas de vértice en hipergrafos.

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

Una cobertura mínima de vértices 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 mínima de vértices, es decir, ${\displaystyle \tau =|V'|}$. La figura inferior muestra ejemplos de coberturas mínimas de vértices en los grafos anteriores.

• El conjunto de todos los vértices es una cobertura de vértices.
• Los extremos de cualquier emparejado máximo forman una cobertura de vértices.
• El grafo bipartito completo ${\displaystyle K_{m,n}}$ tiene una cobertura de vértices mínima de tamaño ${\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}$.

• Un conjunto de vértices es una cobertura 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 máximo independiente.^[1]​

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

INSTANCIA: Grafo ${\displaystyle G}$

SALIDA: Número menor ${\displaystyle k}$ tal que ${\displaystyle G}$ tenga una cobertura de vértices de tamaño ${\displaystyle k}$.

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

INSTANCIA: Sean un grafo ${\displaystyle G}$ y un entero positivo ${\displaystyle k}$.

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

El problema de cobertura de vértices es un problema NP-completo: era uno de veintiún problemas NP-completos de Karp. Se utiliza a menudo en teoría de la complejidad computacional como punto de partida para las demostraciones de NP-dificultad.

Supóngase que cada vértice tiene un coste asociado de ${\displaystyle c(v)\geq 0}$. El problema de cobertura de vértices mínimo (ponderado) se puede formular como el siguiente caso de programación lineal con enteros (ILP).^[2]​

Minimizar	${\displaystyle \textstyle \sum _{v\in V}c(v)x_{v}}$			(minimizar el coste total)
considerando	${\displaystyle x_{u}+x_{v}\geq 1}$	para todo ${\displaystyle \{u,v\}\in E}$		(cubre cada arista del grafo),
	${\displaystyle x_{v}\in \{0,1\}}$	para todo ${\displaystyle v\in V}$.		(cada vértice está en la cubierta de vértices o no)

Este ILP pertenece a la clase más general de ILPs para problemas de recubrimiento. El salto de integridad de este ILP es ${\displaystyle 2}$, 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 de factor ${\displaystyle 2}$ 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 cual cada entrada ${\displaystyle x_{v}}$ 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 son distintas de cero.

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 resolverlo con exactitud para 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 del clique. La cobertura de vértices permanece NP-completa incluso en grafos cúbicos^[3]​ e incluso en grafos planos de grado 3 como máximo.^[4]​

Para grafos bipartitos, la equivalencia entre la cobertura de vértices y la coincidencia máxima descrita por el teorema de Kőnig permite resolver el problema de cobertura de vértices bipartita en tiempo polinómico.

Para grafos en árbol, un algoritmo encuentra una cobertura de vértices mínima en tiempo polinómico. Para ello, encuentra la primera hoja del árbol y añade su padre a la cobertura de vértices mínima. Posteriormente, elimina la hoja, el padre y todas las aristas asociadas, y continúa repetidamente hasta que no queden aristas en el árbol.

Un algoritmo de búsqueda exhaustiva puede resolver el problema en un tiempo 2^kn^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 interesan los valores pequeños de k, se puede resolver el problema en tiempo polinómico. Una técnica algorítmica que funciona aquí se denomina algoritmo de árbol de búsqueda acotado, y su idea es elegir repetidamente un vértice y ramificarlo 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 el tiempo ${\displaystyle O(1.2738^{k}+(k\cdot n))}$.^[5]​ El valor klam de este límite de tiempo (una estimación del valor máximo del parámetro que podría resolverse en un tiempo razonable) es aproximadamente 190. Es decir, a menos que se encuentren mejoras algorítmicas adicionales, este algoritmo solo es adecuado para casos cuyo número de cobertura de vértices sea 190 o inferior. Bajo supuestos razonables de teoría de la complejidad, concretamente para la hipótesis de tiempo exponencial, el tiempo de ejecución no puede mejorarse a 2^o(k), incluso cuando ${\displaystyle n}$ es ${\displaystyle O(k)}$.

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

Se puede encontrar 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, se determina un emparejado M con un algoritmo voraz y se construye una cobertura de vértices C que consta de todos los extremos de las aristas en M. En la siguiente figura, una coincidencia máxima M está marcada 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: supóngase que una arista e no está cubierta por C; entonces M ∪ e es una coincidencia y e ∉ M, lo cual contradice la suposición de que M es máxima. 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 estaría cubierta. Es decir, una cobertura óptima contiene al menos un extremo de cada arista en M, y en total, el conjunto C es como máximo dos veces mayor que la cobertura óptima de vértices.

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

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 ${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$.^[9]​ El problema se puede aproximar con un factor de aproximación ${\displaystyle 2/(1+\delta )}$ en grafos ${\displaystyle \delta }$ densos.^[10]​

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 puede aproximarse con 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 ${\displaystyle {\sqrt {2}}-\epsilon }$ para cualquier ${\displaystyle \epsilon >0}$.^[12]​ Además, si la conjetura del juego único es verdadera, la cobertura mínima de vértices no puede aproximarse con ningún factor constante mejor que 2.^[13]​

Aunque encontrar la cobertura mínima de vértices es equivalente a encontrar el conjunto independiente de tamaño máximo, como se describió anteriormente, ambos problemas no son equivalentes en cuanto a la preservación de la aproximación: el problema del conjunto independiente no tiene aproximación con factor constante a menos que P=NP.

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

APROXIMACIÓN-VÉRTICE-COBERTURA(G)
C= ∅
E'= G.E

while E' ≠ ∅:
    sea (u, v) una arista arbitraria de E'
    C= C ∪ {u, v}
    eliminar de E' cada arista incidente en u o v
return C

La optimización de la cobertura de vértices sirve como modelo para muchos problemas reales y teóricos. Por ejemplo, un establecimiento comercial interesado en instalar la menor cantidad posible de cámaras de videovigilancia que cubran todos los pasillos (aristas) que conectan todas las habitaciones (nodos) de un conjunto de salas interconectadas de la misma planta de un edificio, podría modelar el objetivo como un problema de minimización de la cobertura de vértices. Este problema también se ha utilizado para modelar la eliminación de secuencias repetidas de ADN para aplicaciones de biología sintética y de ingeniería metabólica.^[16]​^[17]​

• Cobertura de aristas
• Problema de la cobertura de vértices
• Problema de la clique
• Conjunto dominante

• Wikimedia Commons alberga una categoría multimedia sobre Cobertura de vértices.
• Weisstein, Eric W. «Vertex Cover». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Minimum Vertex Cover». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Vertex Cover Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Cruces de ríos (y números de Alcuino) ? Numberphile

• Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.