Un conjunto de arcos de retroalimentación ( FAS ) o conjunto de bordes de retroalimentación es un conjunto de bordes que, cuando se eliminan del gráfico, deja un gráfico acíclico. Dicho de otra manera, es un conjunto que contiene al menos un borde de cada ciclo en el gráfico. En la teoría de grafos , un grafo dirigido puede contener ciclos dirigidos , un camino cerrado de aristas unidireccional. En algunas aplicaciones, estos ciclos son indeseables y deseamos eliminarlos y obtener un gráfico acíclico dirigido (DAG). Una forma de hacer esto es simplemente quitar los bordes del gráfico para romper los ciclos.
Estrechamente relacionados están el conjunto de vértices de retroalimentación , que es un conjunto de vértices que contiene al menos un vértice de cada ciclo en el gráfico dirigido, y el árbol de expansión mínimo , que es la variante no dirigida del problema del conjunto de arco de retroalimentación.
Un conjunto de arco de retroalimentación mínimo (uno que no se puede reducir de tamaño eliminando bordes) tiene la propiedad adicional de que, si los bordes en él se invierten en lugar de eliminarse, el gráfico permanece acíclico. Encontrar un pequeño conjunto de aristas con esta propiedad es un paso clave en el dibujo de gráficos en capas . [1] [2]
A veces es deseable dejar caer el menor número posible de bordes, obteniendo un conjunto de arco de retroalimentación mínimo (MFAS), o doblemente un subgrafo acíclico máximo . Este es un problema computacional difícil, para el cual se han ideado varias soluciones aproximadas.
Ejemplo
Como ejemplo simple, considere la siguiente situación hipotética, donde para lograr algo, ciertas cosas deben lograrse antes que otras:
- Tu objetivo es conseguir la cortadora de césped.
- George dice que te dará un piano, pero solo a cambio de una cortadora de césped.
- Harry dice que te dará una cortadora de césped, pero solo a cambio de un microondas.
- Jane dice que te dará un microondas, pero solo a cambio de un piano.
Podemos expresar esto como un problema gráfico. Deje que cada vértice represente un elemento y agregue un borde de A a B si debe tener A para obtener B. Desafortunadamente, no tiene ninguno de los tres elementos, y debido a que este gráfico es cíclico, no puede obtener ninguno. de ellos tampoco.
Sin embargo, suponga que le ofrece a George $ 100 por su piano. Si acepta, esto elimina efectivamente el borde de la cortadora de césped al piano, porque ya no necesita la cortadora de césped para obtener el piano. En consecuencia, el ciclo se rompe y puede intercambiar dos veces para obtener la cortadora de césped. Este borde constituye un conjunto de arco de retroalimentación.
Conjunto de arco de retroalimentación mínimo
Como en el ejemplo anterior, generalmente hay algún costo asociado con la eliminación de un borde. Por esta razón, nos gustaría eliminar la menor cantidad de bordes posible. La eliminación de un borde es suficiente en un ciclo simple, pero en general, calcular el número mínimo de bordes a eliminar es un problema NP-difícil llamado conjunto de arco de retroalimentación mínimo o problema de subgrafo acíclico máximo.
Resultados teóricos
Este problema es particularmente difícil en k gráficas -Edge-conectado para grandes k , donde cada borde cae en muchos ciclos diferentes. La versión de decisión del problema, que es NP-completo , pregunta si todos los ciclos se pueden romper eliminando como máximo k bordes; Este fue uno de los 21 problemas NP-completos de Richard M. Karp , que se muestra reduciendo el problema de cobertura de vértices . [3] [4]
Aunque NP-completo, el problema del conjunto de arco de retroalimentación es manejable con parámetros fijos : existe un algoritmo para resolverlo cuyo tiempo de ejecución es un polinomio fijo en el tamaño del gráfico de entrada (independiente del número de aristas en el conjunto) pero exponencial en el número de aristas en el conjunto de arco de retroalimentación. [5] Alternativamente, un algoritmo manejable de parámetros fijos viene dado por una técnica de programación dinámica que depende sólo exponencialmente de la dimensión del espacio cíclico del gráfico. [6]
El problema del conjunto de arco de retroalimentación mínimo es APX-hard , lo que significa que (asumiendo P ≠ NP ) hay un límite estricto en su calidad de aproximación, una constante c > 1 tal que cada algoritmo de aproximación de tiempo polinomial a veces devolverá un conjunto de aristas más grande que c veces el tamaño óptimo. La demostración implica reducciones que preservan la aproximación desde la cobertura de vértices hasta el conjunto de vértices de retroalimentación , y desde el conjunto de vértices de retroalimentación hasta el conjunto de arcos de retroalimentación. [7] [8] [9] Más específicamente, debido a que la cobertura de vértices no tiene una aproximación mejor que 1.3606 a menos que P ≠ NP, lo mismo es cierto para el conjunto de arco de retroalimentación. Es decir, es posible tomar c = 1.3606 . [10] Si la conjetura de los juegos únicos es cierta, este umbral de inaccesibilidad podría aumentarse a arbitrariamente cerca de 2. [11]
Por otro lado, el algoritmo de aproximación más conocido tiene la relación de aproximación no constante O (log n log log n ). [9] [12] Para el problema dual, de aproximar el número máximo de aristas en un subgrafo acíclico, es posible una aproximación algo mejor que 1/2. [13] [14] Determinar si el conjunto de arco de retroalimentación tiene un algoritmo de aproximación de razón constante, o si es necesaria una razón no constante, sigue siendo un problema abierto.
¿Tiene el problema del conjunto de arco de retroalimentación un algoritmo de aproximación con una razón de aproximación constante?
Si los dígrafos de entrada están restringidos a torneos , el problema resultante se conoce como el problema del conjunto de arco de retroalimentación mínima en los torneos (FAST). Este problema restringido admite un esquema de aproximación de tiempo polinomial , y esto todavía es válido para una versión ponderada restringida del problema. [15] Karpinski y Schudy (2010) dieron un algoritmo subexponencial de parámetros fijos para el FAST ponderado . [dieciséis]
Por otro lado, si los bordes no están dirigidos , el problema de eliminar los bordes para que el gráfico no tenga ciclos es equivalente a encontrar un árbol de expansión mínimo , lo que se puede hacer fácilmente en tiempo polinomial.
Aproximaciones
Se han desarrollado varios algoritmos de aproximación para el problema [17] , incluido el algoritmo aleatorio de Monte Carlo que resuelve el problema en tiempo polinómico con probabilidad arbitraria . [18] Un algoritmo particularmente simple es el siguiente:
- Corrija una permutación arbitraria de los vértices; es decir, etiquete los vértices de 1 a n , eligiendo arbitrariamente qué vértice dar a qué etiqueta.
- Construya dos subgrafos L y R , que contengan los bordes ( u , v ) donde u < v , y aquellos donde u > v , respectivamente.
Ahora, tanto L como R son subgrafos acíclicos de G , y al menos uno de ellos tiene al menos la mitad del tamaño del subgrafo acíclico máximo. [19] : 348
Referencias
- ^ Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998), "Dibujos en capas de dígrafos", Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall , págs. 265-302, ISBN 9780133016154.
- ^ Bastert, Oliver; Matuszewski, Christian (2001), "Dibujos en capas de dígrafos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models , Lecture Notes in Computer Science, 2025 , Springer-Verlag, págs. 87-120, doi : 10.1007 / 3-540-44969-8_5.
- ^ Karp, Richard M. (1972), "Reducibilidad entre problemas combinatorios", Complejidad de los cálculos informáticos , Proc. Simpos. IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, Nueva York: Plenum, págs. 85–103.
- ^ Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, A1.1: GT8, p. 192 , ISBN 0-7167-1045-5.
- ^ 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): 1–19, doi : 10.1145 / 1411509.1411511.
- ^ Hecht, Michael (2017), "Ubicaciones exactas de conjuntos de retroalimentación", Teoría de los sistemas informáticos , 62 (5): 1048–1084, arXiv : 1702.07612 , doi : 10.1007 / s00224-017-9777-6.
- ^ Ausiello, G .; D'Atri, A .; Protasi, M. (1980), "Estructura que conserva las reducciones entre problemas de optimización convexa", Journal of Computer and System Sciences , 21 (1): 136-153, doi : 10.1016 / 0022-0000 (80) 90046-X , MR 0589808.
- ^ Kann, Viggo (1992), Sobre la aproximación de problemas de optimización NP-completo (PDF) , Ph.D. tesis, Departamento de Análisis Numérico y Ciencias de la Computación, Real Instituto de Tecnología, Estocolmo.
- ^ a b Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Conjunto de arco de retroalimentación mínima", Un compendio de problemas de optimización de NP.
- ^ Dinur, Irit ; Safra, Samuel (2005), "Sobre la dureza de aproximar la cobertura mínima de vértices" (PDF) , Annals of Mathematics , 162 (1): 439–485, doi : 10.4007 / annals.2005.162.439. (Versión preliminar en Dinur, Irit (2002). "La importancia de ser parcial". Actas del Trigésimo cuarto Simposio Anual de ACM sobre Teoría de la Computación - STOC '02 : 33. doi : 10.1145 / 509907.509915 . ISBN 1581134959..)
- ^ Khot, Subhash ; Regev, Oded (2008), "La cobertura del vértice puede ser difícil de aproximar dentro de 2 - ε ", Journal of Computer and System Sciences , 74 (3): 335–349, doi : 10.1016 / j.jcss.2007.06.019 , Señor 2384079.
- ^ Incluso, G .; Naor, J .; Schieber, B .; Sudán, M. (1998), "Aproximación de conjuntos de retroalimentación mínimos y cortes múltiples en gráficos dirigidos", Algorithmica , 20 (2): 151-174, doi : 10.1007 / PL00009191 , MR 1484534.
- ^ Berger, B .; Shor, P. (1990), "Algoritmos de aproximación para el problema de subgrafo acíclico máximo", Actas del 1er Simposio ACM-SIAM sobre algoritmos discretos (SODA'90) , Soda '90, págs. 236–243, ISBN 9780898712513.
- ^ Eades, P .; Lin, X .; Smyth, WF (1993), "Una heurística rápida y eficaz para el problema del conjunto de arcos de retroalimentación" , Information Processing Letters , 47 (6): 319–323, doi : 10.1016 / 0020-0190 (93) 90079-O.
- ^ Kenyon-Mathieu, Claire; Schudy, Warren (2007), "Cómo clasificar con pocos errores: un PTAS para el arco de retroalimentación ponderado establecido en los torneos", Proc. 39º Simposio ACM sobre Teoría de la Computación (STOC '07) , págs. 95–103, doi : 10.1145 / 1250790.1250806 , MR 2402432. Véase también la versión ampliada del autor .
- ^ Karpinski, M .; Schudy, W. (2010), "Algoritmos más rápidos para torneos de conjuntos de arco de retroalimentación, agregación de rango de Kemeny y torneo de intermediación", Proc. 21st ISAAC (2010) , Lecture Notes in Computer Science , 6506 , págs. 3-14, arXiv : 1006.4396 , doi : 10.1007 / 978-3-642-17517-6_3.
- ^ Hassin, Refael; Rubinstein, Shlomi (1994). "Aproximaciones para el problema de subgrafo acíclico máximo". Cartas de procesamiento de información . 51 (3): 133–140. CiteSeerX 10.1.1.39.7717 . doi : 10.1016 / 0020-0190 (94) 00086-7 .
- ^ Kudelić, Robert (1 de abril de 2016). "Algoritmo aleatorio de Monte-Carlo para un problema de conjunto de arco de retroalimentación mínima". Soft Computing aplicado . 41 : 235–246. doi : 10.1016 / j.asoc.2015.12.018 .
- ^ Skiena, Steven (2010). El Manual de diseño de algoritmos (2ª ed.). Springer Science + Business Media . págs. 348, 559–561. ISBN 978-1-849-96720-4.