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 . ${\displaystyle G=(V,E)}$ ${\displaystyle k}$

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 ? ${\displaystyle X\subseteq V}$ ${\displaystyle |X|\leq k}$ ${\displaystyle X}$ ${\displaystyle G}$

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 ). ${\displaystyle G[V\setminus X]}$ ${\displaystyle X}$ ${\displaystyle G}$

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 ⁿ ), 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 ⁿ ). ^[4] El problema del conjunto de vértices de retroalimentación dirigido todavía se puede resolver en tiempo O* (1.9977 ⁿ ), 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.

• La completitud APX del problema de cobertura de vértices ; ^[8]
• La existencia de una aproximación que preserva la L-reducción desde el problema de cobertura de vértices hasta ella;
• Algoritmos de aproximación de factores constantes existentes. ^[9]

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

• En lugar de vértices, se puede considerar un conjunto de aristas de retroalimentación : un conjunto de aristas en un grafo no dirigido, cuya eliminación hace que el grafo sea acíclico. El tamaño de un conjunto de aristas de retroalimentación más pequeño en un grafo se llama rango de circuito del grafo. A diferencia del número FVS, el rango de circuito se puede calcular fácilmente: es , donde C es el conjunto de componentes conectados del grafo. El problema de encontrar un conjunto de aristas de retroalimentación más pequeño es equivalente a encontrar un bosque de expansión , lo que se puede hacer en tiempo polinomial . ${\displaystyle |E|-|V|+|C|}$
• El concepto análogo en un grafo dirigido es el conjunto de arcos de retroalimentación (FAS, por sus siglas en inglés), un conjunto de arcos dirigidos cuya eliminación hace que el grafo sea acíclico. Encontrar el FAS más pequeño es un problema NP-hard. ^[9]

Aplicaciones

• En los sistemas operativos , los conjuntos de vértices de retroalimentación desempeñan un papel destacado en el estudio de la recuperación de bloqueos . En el gráfico de espera de un sistema operativo, cada ciclo dirigido corresponde a una situación de bloqueo. Para resolver todos los bloqueos, es necesario abortar algunos procesos bloqueados. Un conjunto mínimo de vértices de retroalimentación en este gráfico corresponde a un número mínimo de procesos que es necesario abortar. ^[14]
• El problema del conjunto de vértices de retroalimentación tiene aplicaciones en el diseño de chips VLSI . ^[15]
• Otra aplicación se encuentra en la teoría de la complejidad. Algunos problemas computacionales en grafos son NP-hard en general, pero pueden resolverse en tiempo polinomial para grafos con un número FVS acotado. Algunos ejemplos son el isomorfismo de grafos ^[16] y el problema de reconfiguración de trayectorias. ^[17]

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. 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

• Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro (1999), "Un algoritmo de 2 aproximaciones para el problema del conjunto de vértices con retroalimentación no dirigida", SIAM Journal on Discrete Mathematics , 12 (3): 289–297 (electrónico), doi :10.1137/S0895480196305124, MR  1710236.
• Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Algoritmos aleatorizados para el problema de corte de bucles", Journal of Artificial Intelligence Research , 12 : 219–234, arXiv : 1106.0225 , doi : 10.1613/jair.638, MR  1765590, S2CID  10243677
• Becker, Ann; Geiger, Dan (1996), "Optimización del método de condicionamiento de Pearl y algoritmos de aproximación de tipo voraz para el problema del conjunto de retroalimentación de vértices", Inteligencia artificial , 83 (1): 167–188, CiteSeerX  10.1.1.25.1442 , doi :10.1016/0004-3702(95)00004-6
• Cao, Yixin; Chen, Jianer; Liu, Yang (2010), "Sobre el conjunto de vértices de retroalimentación: nueva medida y nuevas estructuras", en Kaplan, Haim (ed.), Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Noruega, 21-23 de junio de 2010 , Lecture Notes in Computer Science, vol. 6139, págs. 93–104, arXiv : 1004.1672 , Bibcode :2010LNCS.6139...93C, doi :10.1007/978-3-642-13731-0_10, ISBN 978-3-642-13730-3
• Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (2008), "Algoritmos mejorados para problemas de conjuntos de vértices con retroalimentación", Journal of Computer and System Sciences , 74 (7): 1188–1198, doi :10.1016/j.jcss.2008.05.002, MR  2454063
• Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "Un algoritmo de parámetros fijos para el problema del conjunto de vértices con retroalimentación dirigida", Journal of the ACM , 55 (5), Art. 21, doi :10.1145/1411509.1411511, MR  2456546, S2CID  1547510
• Dinur, Irit ; Safra, Samuel (2005), "Sobre la dificultad de aproximar la cobertura mínima de vértices" (PDF) , Annals of Mathematics , Segunda serie, 162 (1): 439–485, doi :10.4007/annals.2005.162.439, MR  2178966, archivado desde el original (PDF) el 20 de septiembre de 2009 , consultado el 29 de marzo de 2010
• Erdős, Paul ; Pósa, Lajos (1965), "Sobre circuitos independientes contenidos en un grafo" (PDF) , Revista Canadiense de Matemáticas , 17 : 347–352, doi :10.4153/CJM-1965-035-8, S2CID  123981328
• Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "Sobre el problema del conjunto de vértices con retroalimentación mínima: algoritmos exactos y de enumeración.", Algorithmica , 52 (2): 293–307, CiteSeerX  10.1.1.722.8913 , doi :10.1007/s00453-007-9152-0, S2CID  731997
• Fomin, Fedor V.; Villanger, Yngve (2010), "Encontrar subgrafos inducidos mediante triangulaciones mínimas", Proc. 27.° Simposio Internacional sobre Aspectos Teóricos de la Ciencia de la Computación (STACS 2010) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, págs. 383–394, doi : 10.4230/LIPIcs.STACS.2010.2470 , ISBN 9783939897163, S2CID  436224
• Karp, Richard M. (1972), "Reducibilidad entre problemas combinatorios", Proc. Simposio sobre complejidad de los cálculos informáticos, IBM Thomas J. Watson Res. Center, Yorktown Heights, NY , Nueva York: Plenum, págs. 85-103
• Li, Deming; Liu, Yanpei (1999), "Un algoritmo polinomial para encontrar el conjunto de vértices de retroalimentación mínimo de un gráfico simple 3-regular", Acta Mathematica Scientia , 19 (4): 375–381, doi :10.1016/s0252-9602(17)30520-9, MR  1735603
• Razgon, I. (2007), "Computing minimum directioned feedback vertex set in O*(1.9977 ⁿ )", en italiano, Giuseppe F. ; Moggi, Eugenio; Laura, Luigi (eds.), Actas de la 10.ª Conferencia italiana sobre informática teórica (PDF) , World Scientific, págs. 70–81
• Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "Sobre el problema de los conjuntos independientes no separables y el problema de los conjuntos de retroalimentación para gráficos sin grado de vértice superior a tres", Discrete Mathematics , 72 (1–3): 355–360, doi : 10.1016/0012-365X(88)90226-9 , MR  0975556

Libros de texto y artículos de encuestas

• Festa, P.; Pardalos, PM; Resende, MGC (2000), "Problemas de conjuntos de retroalimentación", en Du, D.-Z.; Pardalos, PM (eds.), Handbook of Combinatorial Optimization, Suplemento vol. A (PDF) , Kluwer Academic Publishers, págs. 209–259
• Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, A1.1: GT7, pág. 191, ISBN 978-0-7167-1045-5
• Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Conceptos de sistemas operativos (8.ª ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5