Conjunto de vértices de corte de ciclo

En la teoría de grafos, el conjunto de vértices de corte de ciclo de un gráfico  es el conjunto de vértices cuya eliminación conduce a la ruptura de ciclos . En otras palabras, el conjunto de vértices de corte de ciclo contiene al menos un vértice de cualquier ciclo de gráfico. El problema del conjunto de vértices de corte de ciclo es un problema NP-completo en la teoría de la complejidad computacional . El problema está incluido en la lista de Karp de 21 problemas NP-completos . El problema tiene amplia aplicación en sistemas operativos , bases de datos y desarrollo de VLSI .

Definición

El problema del conjunto de vértices de corte de ciclo  es el siguiente problema de solución :

Dado: Un gráfico (no dirigido o dirigido) y un número positivo . Pregunta: ¿Existe un subconjunto para el cual , tal que con vértices eliminados pertenecientes a , no contenga ciclos ?

El gráfico que queda después de eliminar los vértices pertenecientes al conjunto del gráfico es un bosque generado (para gráficos no dirigidos, o un gráfico acíclico dirigido generado para gráficos dirigidos ). Así, buscar un ciclo mínimo que corte un conjunto de vértices en un grafo equivale a buscar un bosque máximo generado (respectivamente, un grafo acíclico máximo generado en el caso de los grafos dirigidos ).

NP-dificultad

Karp [1] mostró que el problema del conjunto de vértices de corte de ciclo para grafos dirigidos es NP-completo . El problema sigue siendo NP-completo para grafos dirigidos con un grado máximo de arcos entrantes y salientes igual a dos, y para grafos plenarios dirigidos con un grado máximo de arcos entrantes y salientes igual a tres [2] . La reducción de Karp también implica la integridad NP del problema del conjunto de vértices de corte de ciclo en gráficos no dirigidos, y el problema sigue siendo NP-difícil en gráficos con grado máximo cuatro. El problema de un conjunto de vértices de corte de ciclo se puede resolver en tiempo polinomial en gráficos con un grado máximo que no exceda de tres [3] [4] .

Tenga en cuenta que la tarea de eliminar la menor cantidad posible de bordes para romper ciclos (en un gráfico no dirigido) es equivalente a encontrar un árbol de expansión , y esta tarea se puede completar en tiempo polinomial . Por el contrario, el problema de eliminar bordes de un gráfico dirigido para hacerlo acíclico , es decir, el problema de un conjunto de arcos de corte de ciclo , es NP-completo [1] .

Algoritmos exactos

El problema de optimización NP-completo correspondiente de encontrar el tamaño del conjunto mínimo de vértices de corte de ciclo se puede resolver en el tiempo O (1.7347 n ), donde n  es el número de vértices en el gráfico [5] . De hecho, este algoritmo encuentra el bosque máximo generado y el complemento de este bosque será el conjunto de vértices deseado. El número de conjuntos mínimos de vértices de corte de ciclo está limitado a O (1.8638 n ) [6] . El problema del conjunto mínimo de corte de ciclo para un grafo dirigido se puede resolver en el tiempo O* (1.9977 n ), donde n  es el número de vértices en un grafo dirigido dado [7] . Las versiones parametrizadas de problemas orientados y no dirigidos tienen solución paramétrica fija [8] .

Aproximación

El problema es APX-completo , que se deriva directamente de la complejidad APX del problema de cobertura de vértices [9] y de la existencia de una aproximación que conserva la reducción L del problema de cobertura de vértices a este problema [1] . El algoritmo más conocido para grafos no dirigidos tiene un factor de dos [10] .

Bordes

De acuerdo con el teorema de Erdős-Pose, el tamaño del conjunto mínimo de vértices de corte de ciclo está limitado por el factor logarítmico del número máximo de ciclos disjuntos de vértice en un gráfico dado [11] .

Aplicaciones

En los sistemas operativos, el conjunto de vértices de corte de bucle juega un papel destacado en la detección de puntos muertos . En el gráfico de espera del sistema operativo, cada ciclo orientado corresponde a un interbloqueo. Para salir de todos los interbloqueos, se deben finalizar algunos procesos bloqueados. El conjunto mínimo de vértices de corte de ciclo en el gráfico corresponde al número mínimo de procesos que deben interrumpirse [12]

Además, el conjunto de ciclos de corte de vértices tiene aplicaciones en el desarrollo de VLSI [13] .

Notas

  1. ↑ 1 2 3 Karp, 1972 .
  2. ↑ Resultado no publicado debido a Garey y Johnson (Garey, Johnson), véase Garey, Johnson, 1979 : GT7
  3. ↑ Ueno, Kajitani, Gotoh, 1988 .
  4. ↑ Li, Liu, 1999 .
  5. ↑ Fomin, Aldeano, 2010 .
  6. ↑ Fomin, Gaspers, Pyatkin, Razgon, 2008 .
  7. ↑ Razgón, 2007 .
  8. ↑ Chen, Liu, Lu, O'Sullivan, Razgon, 2008 .
  9. ↑ Dinur, Safra, 2005 .
  10. ↑ Becker, Geiger, 1996 . Ver también Bafna, Berman, Fujito, 1999 para un algoritmo de aproximación alternativo con el mismo coeficiente.
  11. ↑ Erdős, Posa, 1965 .
  12. ↑ Silberschatz, Galvin, Gagné, 2008 .
  13. ↑ Festa, Párdalos, Resende, 2000 .

Literatura

Artículos de investigación y libros

Libros de texto y artículos de revisión