LISTA DE PROBLEMAS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Ejemplo de gráfico que tiene una cubierta de vértice que comprende 2 vértices (abajo), pero ninguno con menos.

En la disciplina matemática de la teoría de grafos , una cubierta de vértice (a veces cubierta de nodo ) de un gráfico es un conjunto de vértices de tal manera que cada borde del gráfico incide al menos en un vértice del conjunto. El problema de encontrar una cobertura mínima de vértice es un problema clásico de optimización en informática y 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 la cubierta del vértice , fue uno de los 21 problemas completos de NP de Karpy, por lo tanto, es un problema clásico de NP completo en la teoría de la complejidad computacional . Además, el problema de la cubierta del vértice es manejable con parámetros fijos y un problema central en la teoría de la complejidad parametrizada .

El problema de la cobertura mínima de vértice se puede formular como un programa lineal semi-integral cuyo programa lineal dual es el problema de coincidencia máxima .

Definición [ editar ]

Formalmente, una cubierta de vértice $${\ displaystyle V '} de un gráfico no dirigido $${\ displaystyle G = (V, E)} es un subconjunto de $${\ displaystyle V} tal que $${\ displaystyle uv \ en E \ Rightarrow u \ in V '\ lor v \ in V'}, es decir, es un conjunto de vértices $${\ displaystyle V '} donde cada borde tiene al menos un punto final en la cubierta del vértice $${\ displaystyle V '}. Tal conjunto se dice que cubre los bordes de$${\ displaystyle G}. La siguiente figura muestra dos ejemplos de cubiertas de vértices, con algunas cubiertas de vértices.$${\ displaystyle V '} marcado en rojo.

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

Ejemplos [ editar ]

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

Propiedades [ editar ]

• Un conjunto de vértices es una cubierta de vértice si y solo 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értice más el tamaño de un conjunto independiente máximo ( Gallai 1959).

Problema computacional [ editar ]

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

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

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

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

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

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

El problema de la cubierta de vértice es un problema de NP completo : fue uno de los 21 problemas de Karp con NP completo . A menudo se usa en la teoría de la complejidad computacional como punto de partida para las pruebas de dureza NP .

Formulación de ILP [ editar ]

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

minimizar	$${\ displaystyle \ sum _ {v \ en V} c (v) x_ {v}}			(minimizar el costo total)
sujeto a	$${\ displaystyle x_ {u} + x_ {v} \ geq 1}	para todos $${\ displaystyle \ {u, v \} \ en E}		(cubre todos los bordes del gráfico)
	$${\ displaystyle x_ {v} \ in \ {0,1 \}}	para todos $${\ displaystyle v \ en V}.		(cada vértice está en la cubierta del vértice o no)

Este ILP pertenece a la clase más general de ILP para cubrir problemas . La brecha de integralidad de este ILP es$${\ displaystyle 2}, por lo que su relajación da un factor$${\ displaystyle 2} algoritmo de aproximación para el problema de cobertura de vértice mínimo. Además, la relajación de la programación lineal de ese ILP es semi integral , es decir, existe una solución óptima para la cual cada entrada$${\ displaystyle x_ {v}} es 0, 1/2 o 1.

Evaluación exacta [ editar ]

La variante de decisión del problema de la cubierta del vértice es NP-completo , lo que significa que es poco probable que haya un algoritmo eficiente para resolverlo exactamente para gráficos arbitrarios. La integridad de NP puede demostrarse mediante la reducción de la satisfacción de 3 o, como lo hizo Karp, mediante la reducción del problema de la camarilla . La cubierta del vértice permanece NP-completa incluso en gráficos cúbicos ^[2] e incluso en gráficos planos de grado como máximo 3. ^[3]

Para los gráficos bipartitos , la equivalencia entre la cobertura del vértice y la coincidencia máxima descrita por el teorema de Kőnig permite que el problema de la cubierta del vértice bipartito se resuelva en tiempo polinómico .

Para los gráficos de árbol , un algoritmo encuentra una cubierta de vértice mínima en tiempo polinómico al encontrar la primera hoja en el árbol y agregar su padre a la cubierta de vértice mínimo, luego elimina la hoja y el padre y todos los bordes asociados y continúa repetidamente hasta que no queden bordes el árbol.

Trazabilidad de parámetros fijos [ editar ]

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 cubierta del vértice. La cobertura del vértice es, por lo tanto , manejable con parámetros fijos , y si solo estamos interesados ​​en k pequeña , podemos resolver el problema en tiempo polinómico . 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 bifurcarse recursivamente, con dos casos en cada paso: colocar el vértice actual o todos sus vecinos en la cubierta del vértice. El algoritmo para resolver la cobertura de vértices que logra la mejor dependencia asintótica del parámetro se ejecuta a tiempo$${\ displaystyle O (1.2738 ^ {k} + (k \ cdot n))}. ^[4] El valor de klam de este límite de tiempo (una estimación para el valor del 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 solo para instancias cuyo número de cubierta de vértice es 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$${\ displaystyle n} es $${\ displaystyle O (k)}.

Sin embargo, para gráficos planos , y más generalmente, para gráficos que excluyen algunos gráficos fijos como menores, se puede encontrar una cubierta de vértice de tamaño k a tiempo$${\ displaystyle 2 ^ {O ({\ sqrt {k}})} n ^ {O (1)}}, es decir, el problema es el parámetro subexponencial de parámetro fijo manejable . ^[5] 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$${\ displaystyle 2 ^ {o ({\ sqrt {k}})} n ^ {O (1)}}. ^[6]

Evaluación aproximada [ editar ]

Se puede encontrar una aproximación del factor 2 al tomar repetidamente ambos puntos finales de un borde en la cubierta del vértice y luego eliminarlos del gráfico. Dicho de otro modo, nos encontramos con una máxima coincidencia de M con un algoritmo codicioso y construimos una cubierta vértice C , que consiste en todos los puntos finales de los bordes en M . En la siguiente figura, una coincidencia máxima M está marcada con rojo, y la cubierta del vértice C está marcada con azul.

El conjunto C construido de esta manera es una cubierta de vértice: suponga que un borde e no está cubierto por C ; entonces M  ∪ { e } es una coincidencia y e  ∉  M , lo cual es una contradicción con la suposición de que M es máxima. Además, si e  = { u ,  v } ∈ M , entonces cualquier cubierta de vértice, incluida una cubierta de vértice óptima, debe contener u o v (o ambos); de lo contrario, el borde e no está cubierto. Es decir, una cubierta óptima contiene al menos un punto final de cada borde enM ; en total, el conjunto C es como máximo 2 veces más grande que la cubierta óptima del vértice.

Este algoritmo simple fue descubierto independientemente por Fanica Gavril y Mihalis Yannakakis . ^[7]

Las técnicas más complicadas muestran que existen algoritmos de aproximación con un factor de aproximación ligeramente mejor. Por ejemplo, un algoritmo de aproximación con un factor de aproximación de$${\ displaystyle 2- \ Theta \ left (1 / {\ sqrt {\ log | V |}} \ right)}es conocida. ^[8] El problema puede ser aproximado con un factor de aproximación$${\ displaystyle 2 / (1+ \ delta)} en $${\ displaystyle \ delta}- gráficos densos. ^[9]

Inaproximidad [ editar ]

No se conoce un algoritmo de aproximación de factor constante mejor que el anterior. El problema de cobertura mínima de vértice es APX-complete , es decir, no puede aproximarse bien arbitrariamente a menos que P  =  NP . Usando técnicas del teorema de 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 cualquier grado de vértice suficientemente grande a menos que P  =  NP . ^[10] Además, si la conjetura de los juegos únicos es cierta, entonces la cobertura mínima del vértice no puede aproximarse dentro de un factor constante mejor que 2. ^[11]

Aunque encontrar la cubierta 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 aproximación: el problema del Conjunto Independiente no tiene una aproximación de factor constante a menos que P  =  NP .

Pseudocódigo [ editar ]

1 APROXIMACIÓN - VERTEX - COVER ( G ) : 
2 C  =  ∅ 
3 E ' =  G . E 
4 
5 mientras que  E '≠  ∅ : 
6     let  ( u ,  v )  sea  una  arbitraria  borde  de  E ' 
7     C  =  C  ∪  { u ,  v } 
8     remove  de  E'  Cada  borde  incidente  en  cualquiera de  U  o  V 
9 
10 regreso  C

^[12] [13]

Cubierta de vértice en hipergrafías [ editar ]

Dada una colección de conjuntos, un conjunto que se cruza con todos los conjuntos de la colección en al menos un elemento se denomina conjunto de impacto , y un problema simple de NP difícil es encontrar un conjunto de impacto de menor tamaño o conjunto de impacto mínimo . Al mapear los conjuntos de la colección en hipereduras, esto puede entenderse como una generalización natural del problema de la cubierta de vértices a las hipergrafías, que a menudo se denomina cubierta de vértices para las hipergrafías y, en un contexto más combinatorio, transversal . Las nociones de golpear set y set cover son equivalentes.

Formalmente, permiten H  = ( V ,  E ) un hypergraph con conjunto de vértices V y conjunto hyperedge E . Entonces un conjunto S  ⊆  V se llama conjunto de golpes de H si, para todos los bordes e  ∈  E , contiene S  ∩  e  ≠ ∅. Los problemas de cálculo mínimo golpear conjunto y golpear conjunto se definen como en el caso de gráficos. Tenga en cuenta que recuperamos el caso de las cubiertas de vértices para gráficos simples si el tamaño máximo de las hipereduras es 2.

Si ese tamaño está restringido a d , el problema de encontrar un conjunto mínimo de golpes d permite un algoritmo de aproximación d . Suponiendo la conjetura de los juegos únicos , este es el mejor algoritmo de factor constante posible y, de lo contrario, existe la posibilidad de mejorar la aproximación a d  - 1. ^[11]

Trazabilidad de parámetros fijos [ editar ]

Para el problema del conjunto de golpes, las diferentes parametrizaciones tienen sentido. ^[14] El problema del conjunto de golpes es W [2] -completo para el parámetro OPT, es decir, es poco probable que haya un algoritmo que se ejecute en el tiempo f (OPT) n ^O (1) donde OPT es la cardinalidad de El set de bateo más pequeño. El problema del conjunto de golpes es el parámetro fijo manejable para el parámetro OPT +  d , donde d es el tamaño del borde más grande de la hipergrafía. Más específicamente, hay un algoritmo para golpear el conjunto que se ejecuta en el tiempo d ^OPT n ^O (1) .

Golpeando set y set cover [ editar ]

El problema del conjunto de golpes es equivalente al problema de la cubierta del conjunto : una instancia de la cubierta del conjunto se puede ver como un gráfico bipartito arbitrario, con conjuntos representados por vértices a la izquierda, elementos del universo representados por vértices a la derecha y bordes que representan el inclusión de elementos en conjuntos. La tarea es encontrar un subconjunto de cardinalidad mínima de vértices izquierdos que cubra todos los vértices derechos. En el problema del conjunto de golpes, el objetivo es cubrir los vértices izquierdos usando un subconjunto mínimo de los vértices derechos. Por lo tanto, la conversión de un problema a otro se logra intercambiando los dos conjuntos de vértices.

Aplicaciones [ editar ]

Un ejemplo de una aplicación práctica que involucra el problema del conjunto de golpes surge en la detección dinámica eficiente de las condiciones de carrera . ^[15] En este caso, cada vez que se escribe la memoria global, se almacenan el subproceso actual y el conjunto de bloqueos que posee ese subproceso. Bajo la detección basada en la cerradura, si más tarde otro hilo escribe a ese lugar y hay no una carrera, debe ser porque tiene al menos un bloqueo en común con cada una de las escrituras anteriores. Por lo tanto, el tamaño del conjunto de golpes representa el tamaño mínimo del conjunto de bloqueo para estar libre de carrera. Esto es útil para eliminar eventos de escritura redundantes, ya que los conjuntos de bloqueos grandes se consideran poco probables en la práctica.