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 gráfico es un conjunto de vértices cuya eliminación deja un gráfico sin ciclos ("eliminación" significa eliminar el vértice y todos los bordes adyacentes a él). De manera equivalente, cada FVS contiene al menos un vértice de cualquier ciclo del gráfico. El número de conjunto de vértices de retroalimentación de un gráfico es el tamaño del conjunto de vértices de retroalimentación más pequeño. El problema del conjunto de vértices de retroalimentación mínima es un problema NP-completo ; fue uno de los primeros problemas que demostró ser 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 de FVS es el siguiente:

INSTANCIA: Un gráfico (dirigido o no dirigido) y un número entero positivo . ${\displaystyle G=(V,E)}$ ${\displaystyle k}$

PREGUNTA: ¿Existe un subconjunto tal que, cuando se eliminan todos los vértices de y sus bordes adyacentes , el resto no tiene ciclos ? ${\displaystyle X\subseteq V}$ ${\displaystyle |X|\leq k}$ ${\displaystyle X}$ ${\displaystyle G}$

El gráfico que queda después de eliminarlo es un bosque inducido (o un gráfico acíclico dirigido inducido en el caso de gráficos dirigidos ). Por lo tanto, encontrar un FVS mínimo en un gráfico es equivalente a encontrar un bosque inducido máximo (resp. gráfico acíclico dirigido inducido máximo en el caso de gráficos dirigidos ). ${\displaystyle G[V\setminus X]}$ ${\displaystyle X}$ ${\displaystyle G}$

Dureza NP

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

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

Algoritmos exactos

El correspondiente problema de optimización NP de encontrar el tamaño de un conjunto mínimo de vértices de retroalimentación se puede resolver en el tiempo O (1.7347 ⁿ ), donde n es el número de vértices en el gráfico. ^[3] Este algoritmo en realidad calcula un bosque inducido máximo, y cuando se obtiene dicho bosque, su complemento es un conjunto de vértices de retroalimentación mínimo. El número de conjuntos de vértices de retroalimentación mínimos en un gráfico está limitado por O (1,8638 ⁿ ). ^[4] El problema del conjunto de vértices de retroalimentación dirigida aún se puede resolver en el tiempo O* (1.9977 ⁿ ), donde n es el número de vértices en el gráfico 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 tres máximo, 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 matroide para matroides lineales . ^[7]

Aproximación

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

• El problema de completitud APX de la cobertura de vértices ; ^[8]
• La existencia de una aproximación que preserva la reducción L del problema de cobertura de vértices;
• Algoritmos de aproximación de factor constante existentes. ^[9]

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

Por el contrario, la versión dirigida del problema parece ser mucho más difícil de aproximar. Según la conjetura de los juegos únicos , un supuesto de dureza computacional no probado pero comúnmente utilizado , es NP-difícil aproximar el problema dentro de cualquier factor constante en tiempo polinómico. El mismo resultado de dureza se demostró originalmente para el problema del conjunto de arcos de retroalimentación estrechamente relacionado , ^[11] pero dado que el problema del conjunto de arcos de retroalimentación y el problema del conjunto de vértices de retroalimentación en gráficos dirigidos son reducibles entre sí preservando los tamaños de solución, ^[12] también se cumple para despues.

Límites

Según el teorema de Erdős-Pósa , el tamaño de un conjunto mínimo de vértices de retroalimentación está dentro de un factor logarítmico del número máximo de ciclos disjuntos de vértices 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 gráfico no dirigido, cuya eliminación hace que el gráfico sea acíclico. El tamaño del borde de retroalimentación más pequeño establecido en un gráfico se denomina rango de circuito del gráfico. A diferencia del número FVS, el rango del circuito se puede calcular fácilmente: es , donde C es el conjunto de componentes conectados del gráfico. El problema de encontrar un conjunto de bordes de retroalimentación más pequeño es equivalente a encontrar un bosque expansivo , lo cual se puede hacer en tiempo polinómico . ${\displaystyle |E|-|V|+|C|}$
• El concepto análogo en un gráfico dirigido es el conjunto de arcos de retroalimentación (FAS), un conjunto de arcos dirigidos cuya eliminación hace que el gráfico sea acíclico. Encontrar un FAS más pequeño es un problema NP-difícil. ^[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 puntos muertos . En el gráfico de espera de un sistema operativo, cada ciclo dirigido corresponde a una situación de punto muerto. Para resolver todos los bloqueos, es necesario cancelar algunos procesos bloqueados. Un vértice de retroalimentación mínimo establecido 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 es la teoría de la complejidad. Algunos problemas computacionales en gráficos son NP-difíciles en general, pero pueden resolverse en tiempo polinomial para gráficos con número FVS acotado. Algunos ejemplos son el isomorfismo de grafos ^[16] y el problema de reconfiguración de rutas. ^[17]

Notas

1. resultados inéditos debidos a Garey y Johnson, cf. Garey y Johnson (1979): GT7
2. Ueno, Kajitani y Gotoh (1988); Li y Liu (1999)
3. Fomín y Villanger (2010)
4. Fomín y col. (2008).
5. Razgón (2007).
6. Chen y col. (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 del IEEE sobre fundamentos de la informática . págs. 573–582. doi :10.1109/FOCS.2008.51. ISBN 978-0-7695-3436-7. S2CID  8762205.
12. Incluso, G.; (Seffi) Naor, J.; Schieber, B.; Sudán, M. (1998). "Aproximación de conjuntos mínimos de retroalimentación y multicortes en gráficos dirigidos". Algorítmica . 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 gráficos de número de conjunto de vértices de retroalimentación acotada". En Kaplan, Haim (ed.). Teoría de algoritmos - SWAT 2010 . Apuntes de conferencias sobre informática. vol. 6139. Berlín, Heidelberg: Springer. págs. 81–92. Código Bib : 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 conferencias sobre informática. vol. 11646. 2019. doi : 10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2. S2CID  198996919.

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 de retroalimentación no dirigida", SIAM Journal on Discrete Mathematics , 12 (3): 289–297 (electrónico), doi :10.1137/S0895480196305124, MR  1710236.
• Becker, Ana; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Algoritmos aleatorios para el problema de corte de bucle", Journal of Artificial Intelligence Research , 12 : 219–234, arXiv : 1106.0225 , doi : 10.1613/jair.638, MR  1765590, S2CID  10243677
• Becker, Ana; Geiger, Dan (1996), "Optimización del método de condicionamiento de Pearl y algoritmos de aproximación codiciosos 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. XII Simposio y talleres escandinavos sobre teoría de algoritmos (SWAT 2010), Bergen, Noruega, 21 al 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 de 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 de retroalimentación dirigida", Journal of the ACM , 55 (5), art. 21, doi :10.1145/1411509.1411511, SEÑOR  2456546, S2CID  1547510
• Dinur, Irit ; Safra, Samuel (2005), "Sobre la dureza de aproximar la cobertura mínima de vértices" (PDF) , Annals of Mathematics , Second Series, 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 gráfico" (PDF) , Canadian Journal of Mathematics , 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 de 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 Informática (STACS 2010) , Actas Internacionales de Leibniz en Informática (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 la complejidad de las computadoras, IBM Thomas J. Watson Res. Centro, Yorktown Heights, Nueva York , Nueva York: Plenum, págs. 85-103
• Li, Deming; Liu, Yanpei (1999), "Un algoritmo polinomial para encontrar el conjunto mínimo de vértices de retroalimentación de un gráfico simple de 3 regulares", Acta Mathematica Scientia , 19 (4): 375–381, doi :10.1016/s0252-9602(17) 30520-9, SEÑOR  1735603
• Razgon, I. (2007), "Cálculo del vértice mínimo de retroalimentación dirigida establecido en O*(1.9977 ⁿ )", en Italiano, Giuseppe F .; Moggi, Eugenio; Laura, Luigi (eds.), Actas de la décima conferencia italiana sobre informática teórica (PDF) , World Scientific, págs.
• Ueno, Shûichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "Sobre el problema del conjunto independiente no separable y el problema del conjunto de retroalimentación para gráficos sin un grado de vértice superior a tres", Matemáticas discretas , 72 (1–3): 355–360, doi : 10.1016/0012- 365X(88)90226-9 , SEÑOR  0975556

Libros de texto y artículos de encuestas.

• Festa, P.; Pardalos, PM; Resende, MGC (2000), "Problemas del conjunto de retroalimentación", en Du, D.-Z.; Pardalos, PM (eds.), Manual de optimización combinatoria, 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 integridad NP , WH Freeman, A1.1: GT7, p. 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