En algoritmia y teoría de grafos, un conjunto de arcos de retroalimentación o un conjunto de aristas de retroalimentación en un grafo dirigido es un subconjunto de las aristas del grafo que contiene al menos una arista de cada ciclo del grafo. Eliminar estas aristas del grafo rompe todos los ciclos, produciendo un subgrafo acíclico del grafo dado, a menudo llamado grafo acíclico dirigido. Un conjunto de arcos de retroalimentación con el menor número posible de aristas es un conjunto de arcos de retroalimentación mínimos, y su eliminación deja un subgrafo acíclico máximo. También se utilizan versiones ponderadas de estos problemas de optimización. Si un conjunto de arcos de retroalimentación es mínimo, es decir, si se elimina cualquier arista se obtiene un subconjunto que no es un conjunto de arcos de retroalimentación, entonces tiene una propiedad adicional: invertir todas sus aristas, en lugar de eliminarlas, produce un grafo acíclico dirigido.

Los conjuntos de arcos de retroalimentación tienen aplicaciones en el análisis de circuitos, ingeniería química, resolución de problemas de bloqueo mutuo, voto por orden de preferencia, clasificación de competidores en eventos deportivos, psicología matemática, etología y dibujo de grafos. Encontrar conjuntos de arcos de retroalimentación mínimos y subgrafos acíclicos máximos es NP-difícil; se puede resolver exactamente en tiempo polinómico o en tiempo parametrizado. En tiempo polinómico, el conjunto de arcos de retroalimentación mínimo se puede aproximar mediante un algoritmo de aproximación polilogarítmico, y los subgrafos acíclicos máximos se pueden aproximar dentro de un factor constante. Ambos son difíciles de aproximar más cerca que algún factor constante, un resultado de inaproximabilidad que se puede fortalecer bajo la conjetura del Juego Único. Para torneos en un grafo, el conjunto de arcos de retroalimentación mínimos se puede aproximar con mayor precisión, y para un grafo plano, ambos problemas se pueden resolver con precisión en tiempo polinómico.

Un problema estrechamente relacionado se trata de hallar el conjunto de vértices de retroalimentación, un conjunto de vértices que contiene al menos un vértice de cada ciclo en un grafo dirigido o no dirigido. En grafos, los árboles de expansión son los subgrafos acíclicos más grandes, y el número de aristas eliminadas al formar un árbol de expansión es el rango del circuito.

Aplicaciones

Varios problemas que involucran clasificaciones u ordenamientos pueden resolverse hallando un arco de retroalimentación en el grafo de un torneo, un grafo dirigido con una arista entre cada par de vértices. Invirtiendo las aristas del arco de retroalimentación se obtiene un grafo acíclico dirigido, cuyo único orden topológico puede utilizarse como la clasificación previsible. Entre las aplicaciones de este método se incluyen las siguientes: En competiciones deportivas con sistema de todos contra todos, los resultados de cada partido pueden registrarse dirigiendo una arista del perdedor al ganador. Al hallar un arco de retroalimentación mínimo en el grafo resultante, invirtiendo sus aristas y ordenándolo topológicamente, se obtiene una clasificación de todos los competidores. Entre todas las diferentes maneras de elegir una clasificación, esta minimiza el número total de sorpresas, es decir, partidos en los que un competidor de menor rango vence a uno de mayor rango. Muchos deportes utilizan métodos más sencillos para sistemas de clasificación de torneos de grupo basados en los puntos otorgados por cada partido; estos métodos pueden proporcionar una aproximación constante a la clasificación de mínima sorpresa. En primatología y, de forma más general, en etología, la jerarquía de dominancias se determinan a menudo buscando un orden con la menor cantidad de reversiones en el comportamiento de dominancia observado, otra forma del problema del conjunto de arco de retroalimentación mínimo. En psicología matemática, resulta interesante determinar la clasificación de los sujetos de conjuntos de objetos según un criterio dado, como su preferencia o su percepción del tamaño, basándose en comparaciones por pares entre todos los pares de objetos. El conjunto de arco de retroalimentación mínimo en un gráfico de torneo proporciona una clasificación que discrepa con el menor número posible de resultados por pares. Alternativamente, si estas comparaciones resultan en probabilidades independientes para cada ordenamiento por pares, entonces el máxima verosimilitud de la clasificación general puede obtenerse convirtiendo estas probabilidades en log-likelihoods y hallando un arco de retroalimentación de peso mínimo establecido en el torneo resultante. El mismo ordenamiento de máxima verosimilitud puede utilizarse para seriation, el problema en estadística y análisis exploratorio de datos de organizar los elementos en un ordenamiento lineal, en los casos en que se disponga de datos que proporcionen comparaciones por pares entre los elementos. En el sistema de voto por orden de preferencia, el método de Kemeny-Young puede describirse como la búsqueda de un ordenamiento que minimice la suma, sobre pares de candidatos, del número de votantes que prefieren el ordenamiento opuesto para ese par. Esto se puede formular y resolver como un problema de conjunto de arcos de retroalimentación de peso mínimo, en el que los vértices representan candidatos, las aristas se dirigen para representar al ganador de cada enfrentamiento directo, y el costo de cada arista representa el número de votantes que se sentirían insatisfechos si se otorgara una clasificación más alta al perdedor del enfrentamiento directo.

Otra aplicación temprana de los conjuntos de arcos de retroalimentación se relacionó con el diseño de circuitos secuenciales, en los que las señales pueden propagarse en ciclos a través del circuito en lugar de progresar siempre de las entradas a las salidas. En tales circuitos, un conjunto de arcos de retroalimentación mínimo caracteriza el número de puntos en los que la amplificación es necesaria para permitir que las señales se propaguen sin pérdida de información. En los circuitos síncronos hechos de componentes asíncronos, la sincronización se puede lograr colocando puertas sincronizadas en los bordes de un conjunto de arcos de retroalimentación. Además, cortar un circuito en un conjunto de arcos de retroalimentación reduce el circuito restante a un sistema combinatorio, simplificando su análisis, y el tamaño del conjunto de arcos de retroalimentación controla cuánto análisis adicional se necesita para comprender el comportamiento del circuito a través del corte. De forma similar, en diagramas de flujo de procesos y en ingeniería química, romper las aristas de un diagrama de flujo de proceso en un conjunto de arcos de retroalimentación y adivinar o probar todas las posibilidades de valores en esas aristas permite analizar sistemáticamente el resto del proceso gracias a su aciclicidad. En esta aplicación, la idea de romper aristas de esta manera se denomina desgarro.

En dibujo de grafos en capas, los vértices de un grafo dirigido dado se dividen en una secuencia ordenada de subconjuntos (las capas del dibujo), y cada subconjunto se coloca en una línea horizontal de este dibujo, con las aristas extendiéndose hacia arriba y hacia abajo entre estas capas. En este tipo de dibujo, es deseable que la mayoría o la totalidad de las aristas estén orientadas consistentemente hacia abajo, en lugar de mezclarlas, para que las relaciones de alcanzabilidad en el dibujo sean más evidentes. Esto se logra encontrando un conjunto de arcos de retroalimentación mínimo, invirtiendo las aristas de dicho conjunto y seleccionando la partición en capas de forma coherente con el orden topológico del grafo acíclico resultante.. Los conjuntos de arcos de retroalimentación también se han utilizado para un subproblema diferente del dibujo de grafos en capas: la ordenación de vértices dentro de pares consecutivos de capas..

En la resolución de problemas de bloqueo mutuo en un sistema operativo, el problema de eliminar el menor número de dependencias para romper un bloqueo mutuo puede modelarse como el de encontrar un conjunto mínimo de arcos de retroalimentación. Sin embargo, debido a la dificultad computacional para encontrar este conjunto y a la necesidad de velocidad en los componentes del sistema operativo, en esta aplicación se suelen utilizar procedimientos heurísticos en lugar de algoritmos exactos.

Algoritmos Equivalencias El conjunto de arcos de retroalimentación mínimo y el subgrafo acíclico máximo son equivalentes a efectos de optimización exacta, ya que uno es el complemento del otro. Sin embargo, en cuanto a la complejidad parametrizada y a la aproximación, difieren, ya que el análisis utilizado para estos tipos de algoritmos depende del tamaño de la solución y no solo del tamaño del grafo de entrada, y el conjunto de arcos de retroalimentación mínimos y el subgrafo acíclico máximo tienen tamaños diferentes.

Un conjunto de arcos de retroalimentación de un grafo dado es el mismo que un conjunto de vértices de retroalimentación de un grafo lineal dirigido Aquí, un conjunto de vértices de retroalimentación se define de forma análoga a un conjunto de arcos de retroalimentación, como un subconjunto de los vértices del grafo cuya supresión eliminaría todos los ciclos. El grafo lineal de un grafo dirigido tiene un vértice para cada arista y una arista para cada camino de dos aristas En la otra dirección, el conjunto de vértices de retroalimentación mínimo de un grafo dado puede obtenerse a partir de la solución de un problema de conjunto de arcos de retroalimentación mínimos en un grafo obtenido al dividir cada vértice de en dos vértices, uno para las aristas entrantes y otro para las aristas salientes. Estas transformaciones permiten obtener algoritmos exactos para conjuntos de arcos de retroalimentación y para conjuntos de vértices de retroalimentación que se convertirán entre sí, con una traslación apropiada de sus límites de complejidad. Sin embargo, esta transformación no preserva la calidad de aproximación para el problema del subgrafo acíclico máximo.

Tanto en soluciones exactas como aproximadas del problema del conjunto de arcos de retroalimentación, basta con resolver por separado cada componente fuertemente conexo del grafo dado y descomponerlos aún más hasta obtener sus componentes biconectados, dividiéndolos en los vértices de articulación. La elección de la solución dentro de cualquiera de estos subproblemas no afecta a los demás, y las aristas que no aparecen en ninguno de estos componentes son inútiles para su inclusión en el conjunto de arcos de retroalimentación. Cuando uno de estos componentes puede separarse en dos subgrafos inconexos eliminando dos vértices, se aplica una descomposición más compleja, que permite dividir el problema en subproblemas derivados de los componentes triconectados de sus componentes fuertemente conexos.

Exacto Una forma de encontrar el conjunto mínimo de arcos de retroalimentación es buscar un orden de vértices tal que la menor cantidad posible de aristas se dirijan desde vértices posteriores a vértices anteriores en el orden. Buscar todos las permutaciones de un grafo de requeriría un pero un método de programación dinámica basado en el algoritmo de Held-Karp puede encontrar la permutación óptima en utilizando también una cantidad exponencial de espacio de memoria. Un algoritmo divide y vencerás que prueba todas las particiones de los vértices en dos subconjuntos iguales y recurre dentro de cada subconjunto, puede resolver el problema en utilizando pSPACE.