# Conjunto de arcos de realimentação

Em teoria dos grafos, um grafo direcionado pode conter ciclos direcionados, um loop formado por um ciclo através de arestas. Em algumas aplicações, estes ciclos são indesejados, e queremos eliminá-los para obter um grafo acíclico direcionado (GAD). Uma maneira de fazer isso é simplesmente retirar arestas do grafo para remover os ciclos. Um conjunto de arcos de realimentação (CAR) ou conjunto de arestas de realimentação é um conjunto de arestas que, quando são retiradas do grafo, levam a um GAD. Em outras palavras é um conjunto que contém pelo menos uma aresta de cada ciclo existente no grafo.
Estreitamente relacionado é o conjunto de vértices de realimentação, que é um conjunto de vértices que contém ao menos um vértice de cada ciclo no grafo direcionado, e a árvore de extensão mínima, que é a forma não dirigida do problema do conjunto de arcos de realimentação.
Um conjunto de arcos de realimentação mínimo (que não pode ser reduzido em tamanho por remoção de quaisquer arestas) tem a propriedade adicional de que, se as arestas forem invertidas ao invés de removidas, então o grafo permanece acíclico. Encontrar um pequeno conjunto de arestas com essa propriedade é um passo fundamental no desenho do grafo em camadas.
Às vezes é desejável retirar tão poucas arestas quanto possível, obtendo um conjunto de arcos de realimentação mínimo, ou um subgrafo acíclico máximo. Isto é um problema computacional difícil, para o qual várias soluções aproximadas foram criadas.

## Exemplo

Como um exemplo simples, considere a seguinte situação hipotética, onde a fim de alcançar algo, certas coisas devem ser alcançadas antes de outras coisas:
* Seu objetivo é obter um cortador de grama.
* George diz que ele vai dar-lhe um piano, mas apenas em troca de um cortador de grama.
* Harry diz que vai lhe dar um cortador de grama, mas apenas em troca de um micro-ondas.
* Jane diz que ela vai lhe dar um micro-ondas, mas apenas em troca de um piano.
Podemos expressar isso como um problema de grafo. Pegue cada vértice que representa um item e adicione uma aresta de A para B, se você deve ter A para poder obter B. Infelizmente, você não tem nenhum dos três itens, e como este grafo é cíclico, você não pode obter nenhum deles também.
No entanto, suponha que você ofereça $100 a George pelo piano. Se ele aceitar, isso efetivamente remove a aresta do cortador de grama para o piano, porque você não precisa mais do cortador de grama para obter o piano. Consequentemente, o ciclo é quebrado, e você pode negociar duas vezes para obter o cortador de grama. Esta aresta constitui um conjunto de arcos de realimentação.

## Conjunto de arcos de realimentação mínimo

Tal como no exemplo acima, há geralmente um custo associado com a remoção de uma aresta. Por esta razão, gostaríamos de remover tão poucas arestas quanto possível. Remover uma das arestas em um ciclo simples é suficiente, mas, em geral, descobrir o número mínimo de arestas a serem removidas é um problema NP-Difícil chamado de conjunto de arcos de realimentação mínimo ou problema do subgrafo acíclico máximo.

### Resultados Teóricos

Este problema é particularmente difícil no Grafo k-aresta-conexo para largura k, onde cada aresta recai em muitos ciclos diferentes. A versão de decisão do problema, que é NP-completo, pergunta se todos os ciclos podem ser quebrados pela remoção da maior quantidade de k arestas; este foi um dos 21 problemas NP-completos de Richard M. Karp, provados a partir da redução da cobertura de vértices.
Embora NP-completo, o conjunto de arcos de realimentação é um ftp: existe um algoritmo para solucioná-lo cujo tempo de execução é um polinômio fixado no tamanho do grafo de entrada (independentemente do número de arestas no conjunto) mas exponencial no número de vértices no conjunto de arcos de realimentação.
Viggo Kann mostrou em 1992 que o problema do conjunto de arcos de realimentação mínimo é Apx-difícil, isso significa que existe uma constante c, tal que, assumindo que P≠NP, não existe um algoritmo de aproximação de tempo polinomial que sempre encontra um conjunto de arestas no máximo c vezes maior que o resultado ótimo. A partir de 2006, o maior valor de c para o qual um resultado de impossibilidade é conhecido é c = 1.3606. O melhor algoritmo de aproximação conhecido tem tempo O(log n log log n). Para o duplo problema de aproximar o máximo número de arestas em um subgrafo acíclico, uma aproximação um pouco melhor que 1/2 é possível.
Se os dígrafos de entrada são restritos a torneios (do inglês, tournaments), o problema resultante é conhecido como o problema de conjunto de arcos de realimentação mínimo sobre torneios (FAST). Este problema restrito admite um esquema de aproximação de tempo polinomial, e isso ainda é valido para a versão ponderada do problema. Um algoritmo de parâmetro fixo subexponencial para ponderar rapidamente FAST foi dado por Karpinski & Schudy (2010).
Por outro lado, se as arestas são não-direcionadas, o problema de remover arestas para tornar o grafo livre de ciclo é equivalente a encontrar uma Arvore de extensão mínima, a qual pode ser feita facilmente em tempo polinomial.

### Aproximações

Vários algoritmos de aproximação para o problema têm sido desenvolvidos. Um algoritmo particularmente simples é descrito a seguir:
* Fixe uma permutação arbitrária dos vértices, ou seja, rotule-os de 1 a n.
* Construa dois subgrafos L e R, que contém as arestas (u, v), onde u < v, e aqueles em que u > v, respectivamente.
Agora ambos L e R são subgrafos acíclicos de L, e pelo menos um deles é pelo menos metade do tamanho do subgrafo máximo acíclico.