En teoría de grafos, un gráfico dirigido puede contener ciclos dirigidos , un anillo de arcos que tienen la misma dirección. En algunas aplicaciones, tales ciclos no son deseables, podemos eliminarlos y obtener un gráfico acíclico dirigido (Gráfico acíclico dirigido, DAG). Una forma de eliminar los arcos es simplemente eliminar los arcos del gráfico. Un conjunto de arcos de retroalimentación ( FAS ) o un conjunto de borde de corte de ciclo es un conjunto de arcos que, cuando se eliminan de un gráfico, forman un DAG. Visto desde un ángulo diferente, es un conjunto que contiene al menos un borde de cada ciclo del gráfico.
Un concepto estrechamente relacionado es el conjunto de vértices de corte de ciclo , que incluye al menos un vértice de cada ciclo de un gráfico dirigido, y el árbol de expansión mínimo , que es una versión no dirigida del problema de encontrar un conjunto de arcos de corte de ciclo.
Un conjunto mínimo de arcos de corte de ciclo (que no se puede reducir de tamaño eliminando los bordes) tiene la propiedad adicional de que si sus bordes 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 la superposición de un gráfico [1] [2] .
A veces es deseable descartar la menor cantidad de arcos posible, formando el conjunto de arcos de corte de ciclo más pequeño , o el subgrafo acíclico dual más grande . El problema es un problema computacional complejo para el cual se han desarrollado algunas soluciones aproximadas.
Como un ejemplo simple, imagine la siguiente situación hipotética en la que se debe hacer algo para obtener algo:
Podemos expresar esta situación como un problema en un gráfico. Deja que cada vértice represente un elemento, y agregamos un arco de A a B si debemos tener A para obtener B. Desafortunadamente, no tienes ninguna de esas tres cosas, y dado que el gráfico es cíclico, no puedes tener cualquiera de esas cosas.
Sin embargo, suponga que le da a George $100 por su piano. Si los acepta, le quitará el arco de la cortadora de césped al piano. Así, el ciclo se rompe y puedes hacer dos canjes para conseguir el codiciado cortacésped. Este arco único constituye un conjunto de arcos de corte cíclico.
Como en el ejemplo anterior, generalmente hay algún precio asociado con la ruptura del arco. Por esta razón, es deseable eliminar la menor cantidad posible de arcos. Eliminar un solo arco es suficiente para romper un ciclo simple, pero en general, encontrar el menor número de arcos para eliminar es un problema NP-difícil y se denomina el conjunto de arcos de corte de ciclo más pequeño o el problema de subgrafo acíclico más grande.
Este problema es particularmente difícil para gráficos conectados por k bordes para k grandes , donde cada arco termina en muchos ciclos diferentes. El problema de resolución , que es NP-completo , pregunta si es posible cortar todos los ciclos eliminando como máximo k arcos. Este problema está incluido en la lista de Karp de 21 problemas NP-completos [3] [4] .
Al ser NP-completo, el problema de encontrar un conjunto de ciclos de corte de arcos tiene una solución paramétrica fija : hay un algoritmo para resolverlo, cuyo tiempo de ejecución depende polinomialmente del tamaño del gráfico de entrada (pero no dependen del número de aristas), pero el tiempo depende exponencialmente de la cantidad de aristas en el conjunto de arcos de corte cíclico [5] .
Viggo Kann mostró en 1992 que el problema de encontrar el conjunto mínimo de arcos de corte de ciclo es APX-hard , lo que significa que hay una constante c tal que, asumiendo P≠NP, no hay un algoritmo de aproximación de tiempo polinomial , que siempre encuentra un conjunto de aristas como máximo c veces mayor que la óptima [6] [7] . Para 2006, el mayor valor de c , para el cual se sabe que no existe tal algoritmo, es igual a c = 1.3606 [8] . El algoritmo de aproximación más conocido tiene una estimación de O (log n log log n ) [7] [9] . Para el problema dual de aproximar el número de aristas en un subgrafo acíclico, es posible un algoritmo con un coeficiente ligeramente mejor que 1/2 [10] [11] .
Si los dígrafos de entrada están restringidos a torneos , el problema se conoce como problema de conjunto de arco de retroalimentación mínimo en torneos ( FAST ). Este problema restringido permite un esquema de tiempo polinomial aproximado y esta afirmación sigue siendo válida para la versión ponderada restringida del problema [12] . Karpinski y Schudi [13] propusieron un algoritmo con un parámetro subexponencial fijo para FAST ponderado .
Por otro lado, si los bordes no están dirigidos , la tarea de eliminar bordes para llegar a un gráfico sin ciclos es equivalente a encontrar un árbol de expansión mínimo , lo que se puede hacer fácilmente en tiempo polinomial.
Se han desarrollado algunos algoritmos de aproximación para el problema [14] . Un algoritmo muy simple es el siguiente:
Ahora, tanto L como R son subgrafos acíclicos de G , y al menos uno de estos gráficos tiene como máximo la mitad del tamaño de un subgrafo acíclico máximo [15] .