stringtranslate.com

Conjunto de vértices de retroalimentación

En la disciplina matemática de la teoría de grafos , un conjunto de vértices de retroalimentación (FVS) de un grafo es un conjunto de vértices cuya eliminación deja un grafo sin ciclos ("eliminación" significa eliminar el vértice y todas las aristas adyacentes a él). Equivalentemente, cada FVS contiene al menos un vértice de cualquier ciclo en el grafo. El número de conjunto de vértices de retroalimentación de un grafo es el tamaño de un conjunto de vértices de retroalimentación más pequeño. El problema del conjunto mínimo de vértices de retroalimentación es un problema NP-completo ; fue uno de los primeros problemas que se demostró que era NP-completo . Tiene amplias aplicaciones en sistemas operativos , sistemas de bases de datos y diseño de chips VLSI .

Definición

El problema de decisión FVS es el siguiente:

INSTANCIA: Un gráfico (dirigido o no dirigido) y un entero positivo .
PREGUNTA: ¿Existe un subconjunto con tal que, cuando se eliminan todos los vértices de y sus aristas adyacentes de , el resto está libre de ciclos ?

El gráfico que queda después de eliminar de es un bosque inducido (o un gráfico acíclico dirigido inducido en el caso de los gráficos dirigidos ). Por lo tanto, encontrar un FVS mínimo en un gráfico es equivalente a encontrar un bosque inducido máximo (o un gráfico acíclico dirigido inducido máximo en el caso de los gráficos dirigidos ).

Dureza NP

Karp (1972) demostró que el problema FVS mínimo para grafos dirigidos es NP-completo . El problema sigue siendo NP-completo en grafos dirigidos con máximo grado de entrada y de salida de dos, y en grafos planos dirigidos con máximo grado de entrada y de salida de tres. [1]

La reducción de Karp también implica la NP-completitud del problema FVS en grafos no dirigidos , donde el problema permanece NP-duro en grafos de grado máximo cuatro. El problema FVS puede resolverse en tiempo polinomial en grafos de grado máximo tres como máximo. [2]

Algoritmos exactos

El problema de optimización NP correspondiente de encontrar el tamaño de un conjunto mínimo de vértices de retroalimentación se puede resolver en tiempo O (1.7347 n ), donde n es el número de vértices en el grafo. [3] Este algoritmo en realidad calcula un bosque inducido máximo, y cuando se obtiene dicho bosque, su complemento es un conjunto mínimo de vértices de retroalimentación. El número de conjuntos mínimos de vértices de retroalimentación en un grafo está limitado por O (1.8638 n ). [4] El problema del conjunto de vértices de retroalimentación dirigido todavía se puede resolver en tiempo O* (1.9977 n ), donde n es el número de vértices en el grafo dirigido dado. [5] Las versiones parametrizadas de los problemas dirigidos y no dirigidos son manejables con parámetros fijos . [6]

En gráficos no dirigidos de grado máximo tres, el problema del conjunto de vértices de retroalimentación se puede resolver en tiempo polinomial , transformándolo en una instancia del problema de paridad de matroides para matroides lineales . [7]

Aproximación

El problema no dirigido es APX-completo . Esto se desprende de los siguientes hechos.

El algoritmo de aproximación más conocido en gráficos no dirigidos es por un factor de dos. [10]

Por el contrario, la versión dirigida del problema parece ser mucho más difícil de aproximar. Bajo la conjetura de juegos únicos , un supuesto de dificultad computacional no probado pero de uso común , es NP-difícil aproximar el problema dentro de cualquier factor constante en tiempo polinomial. El mismo resultado de dificultad se demostró originalmente para el problema de conjunto de arcos de retroalimentación estrechamente relacionado , [11] pero dado que el problema de conjunto de arcos de retroalimentación y el problema de conjunto de vértices de retroalimentación en grafos dirigidos son reducibles entre sí mientras se preservan los tamaños de las soluciones, [12] también se cumple para este último.

Límites

Según el teorema de Erdős–Pósa , el tamaño de un conjunto de vértices de retroalimentación mínimo está dentro de un factor logarítmico del número máximo de ciclos de vértices disjuntos en el gráfico dado. [13]

Conceptos relacionados

Aplicaciones

Notas

  1. ^ Resultados no publicados debidos a Garey y Johnson, cf. Garey & Johnson (1979): GT7
  2. ^ Ueno, Kajitani y Gotoh (1988); Li y Liu (1999)
  3. ^ Fomin y Villanger (2010)
  4. ^ Fomin y otros (2008).
  5. ^ Razgon (2007).
  6. ^ Chen y otros (2008).
  7. ^ Ueno, Kajitani y Gotoh (1988).
  8. ^ Dinur y Safra 2005
  9. ^Por Karp (1972)
  10. ^ Becker y Geiger (1996). Véase también Bafna, Berman y Fujito (1999) para un algoritmo de aproximación alternativo con la misma relación de aproximación.
  11. ^ Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008). "Superar el orden aleatorio es difícil: inaproximabilidad del subgrafo acíclico máximo". 2008 49.° Simposio anual IEEE sobre fundamentos de la informática . págs. 573–582. doi :10.1109/FOCS.2008.51. ISBN 978-0-7695-3436-7.S2CID8762205  .​
  12. ^ Even, G.; (Seffi) Naor, J.; Schieber, B.; Sudan, M. (1998). "Aproximación de conjuntos de retroalimentación mínimos y multicortes en gráficos dirigidos". Algorithmica . 20 (2): 151–174. doi :10.1007/PL00009191. ISSN  0178-4617. S2CID  2437790.
  13. ^ Erdős y Pósa (1965).
  14. ^ Silberschatz, Galvin y Gagne (2008).
  15. ^ Festa, Pardalos y Resende (2000).
  16. ^ Kratsch, Stefan; Schweitzer, Pascal (2010). "Isomorfismo para grafos de un conjunto de vértices de retroalimentación acotado". En Kaplan, Haim (ed.). Algorithm Theory - SWAT 2010 . Apuntes de clase en informática. Vol. 6139. Berlín, Heidelberg: Springer. págs. 81–92. Código Bibliográfico :2010LNCS.6139...81K. doi :10.1007/978-3-642-13731-0_9. ISBN 978-3-642-13731-0.
  17. ^ Algoritmos y estructuras de datos (PDF) . Apuntes de clases de informática. Vol. 11646. 2019. doi :10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2.S2CID198996919  .​

Referencias

Artículos de investigación

Libros de texto y artículos de encuestas