Problema de cobertura de vértices

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de mayo de 2020; las comprobaciones requieren 3 ediciones .

El problema de la cobertura de vértices es un problema informático NP-completo en el campo de la teoría de grafos . A menudo se usa en la teoría de la complejidad para probar la completitud NP de problemas más complejos.

Definición

La cobertura de vértices de un grafo no dirigido es el conjunto de sus vértices , tal que, para cada arista del grafo, al menos uno de los extremos entra en el vértice desde . $G=(V,E)$ $S$ $S$

El tamaño de una cubierta de vértice es el número de vértices que contiene.

Ejemplo: el gráfico de la derecha tiene una cubierta de vértice de tamaño 4. Sin embargo, esta no es la cubierta de vértice más pequeña, porque hay cubiertas de vértice más pequeñas, como y . $\{1,3,5,6\}$ $\{2,4,5\}$ $\{1,2,4\}$

El problema de la cobertura de vértices es encontrar el tamaño más pequeño de cobertura de vértices para un gráfico dado (este tamaño se denomina número de cobertura de vértices del gráfico ).

Entrada: Conde .

G=(V,E)

Resultado: el conjunto es la cubierta de vértice más pequeña del gráfico .

C\subseteq V

GRAMO

Además, la pregunta se puede plantear como un problema de resolución equivalente :

Entrada: un gráfico y un entero positivo .

GRAMO

k

Pregunta: ¿Hay una cubierta de vértice para un gráfico de tamaño como máximo ?

C

GRAMO

k

El problema de la cobertura de vértices es similar al problema de los conjuntos independientes . Dado que un conjunto de vértices es una cubierta de vértices si y solo si su complemento es un conjunto independiente, los problemas se reducen entre sí. $C$ $V\setminus C$

NP-completo

Dado que el problema de la cobertura de vértices es NP-completo , desafortunadamente no existen algoritmos conocidos para resolverlo en tiempo polinomial. Sin embargo, existen algoritmos de aproximación que brindan una solución "aproximada" a este problema en tiempo polinomial: puede encontrar una cobertura de vértices en la que el número de vértices no sea más del doble del mínimo posible.

Uno de los primeros enfoques para resolver el problema que viene a la mente es la aproximación a través del algoritmo voraz : es necesario agregar vértices con el máximo número de vecinos a la cubierta de vértices hasta que se resuelva el problema, pero tal solución no tiene aproximación. para cualquier constante . $\rho$ $\rho$

Otra solución es encontrar la coincidencia máxima en el gráfico dado y elegir el conjunto como la cubierta de vértice . La corrección de dicho algoritmo se prueba por contradicción: si no es una cubierta de vértice (no necesariamente la más pequeña), es decir , entonces no es una coincidencia máxima. El factor de aproximación se prueba de la siguiente manera: Sea , donde es el número de independencia de la gráfica , y es la mayor coincidencia de la gráfica . Entonces el factor de aproximación es . ${\ estilo de visualización M \ en E}$ $G=(V,E)$ $C=\bigcup _{e\in M}e$ $C$ $\existe e\colon e\cap C=\emptyset$ $METRO$ ${\ estilo de visualización \ tau (G) = | V | - \ alfa (G)}$ $\ alfa (G)$ $GRAMO$ $M_{máx}(G)$ $GRAMO$ ${\frac {2\cdot |M|}{\tau (G)))\leqslant {\frac {2\cdot |M_{max}(G)|}{\tau (G)))\ leqslant {\frac {2\cdot |M_{max}(G)|}{|M_{max}(G)|}}=2$

En general, el problema de la cobertura de vértices se puede aproximar con un factor . $2-{\frac {\log \log n}{2\cdot \log n))$

El problema de la cobertura de vértices en grafos bipartitos

En grafos bipartitos , el problema de cobertura de vértices es resoluble en tiempo polinomial, ya que se reduce al mayor problema de emparejamiento ( teorema de König ).

Enlaces

Literatura

Thomas H. Kormen et al Capítulo 36. NP-Completitud // Algoritmos: Construcción y Análisis = INTRODUCCIÓN A LOS ALGORITMOS. - 1ª ed. - M. : Centro de Moscú para la Educación Matemática Continua, 2001. - P. 866.

Problemas NP-completos
Problema de maximización del apilamiento (packing)	Envasado en contenedores embalaje bidimensional embalaje lineal embalaje por peso embalaje por valor El problema de la mochila
teoría de grafos teoría de conjuntos	Problema de cobertura de vértices Haga clic en problema El problema de un conjunto independiente (conjunto) Establecer problema de cobertura Problema de Steiner El problema del viajante de comercio Problema generalizado del viajante de comercio
Problemas algorítmicos	Problema de satisfacibilidad para fórmulas booleanas (en forma normal conjuntiva)
Juegos de lógica y rompecabezas.	Etiquetas generalizadas (juego en N 2 -1) problema de solución más corta Problemas cuyas soluciones se aplican en Tetris Problema de sudoku generalizado Problema de llenado de cuadrados latinos La tarea de Kakuro
Clases de dificultad La investigación de operaciones Mejoramiento optimización combinatoria Matemáticas Aplicadas Teoría de Algoritmos Programación dinámica 21 Problema de Karp NP-completo