Conjunto de arcos de realimentação

Este grafo não contém ciclos: Não é possível chegar em um vértice (ponto) e voltar para o mesmo ponto, seguindo as conexões nas direções indicadas pelas setas.

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.

Referências

1. Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302, ISBN 9780133016154.
2. Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea, Drawing Graphs: Methods and Models, Lecture Notes in Computer Science 2025, Springer-Verlag, pp. 87–120,doi:10.1007/3-540-44969-8_5.
3. Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103.
4. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.1: GT8, p. 192, ISBN 0-7167-1045-5.
5. Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM 55 (5), doi:10.1145/1411509.1411511.
6. Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF), Ph.D. thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm.
7. Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", A compendium of NP optimization problems.
8. Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics 162 (1): 439–485, doi:10.4007/annals.2005.162.439. (Preliminary version in STOC 2002, titled "The importance of being biased", doi:10.1145/509907.509915.)
9. Even, G.; Naor, J.; Schieber, B.; Sudan, M. (1998), "Approximating minimum feedback sets and multicuts in directed graphs", Algorithmica 20 (2): 151–174, doi:10.1007/PL00009191, MR 1484534.
10. Berger, B.; Shor, P. (1990), "Approximation algorithms for the maximum acyclic subgraph problem", Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA’90), pp. 236–243.
11. Eades, P.; Lin, X.; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters 47: 319–323, doi:10.1016/0020-0190(93)90079-O.
12. Kenyon-Mathieu, Claire; Schudy, Warren (2007), "How to rank with few errors: a PTAS for weighted feedback arc set on tournaments", Proc. 39th ACM Symposium on Theory of Computing (STOC '07), pp. 95–103,doi:10.1145/1250790.1250806, MR 2402432. See also author's extended version.
13. Karpinski, M.; Schudy, W. (2010), "Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament", Proc. 21st ISAAC (2010), Lecture Notes in Computer Science 6506, pp. 3–14,doi:10.1007/978-3-642-17517-6_3.
14. Hassin, Refael; Rubinstein, Shlomi (1994). "Approximations for the maximum acyclic subgraph problem". Information Processing Letters 51 (3): 133–140. doi:10.1016/0020-0190(94)00086-7. CiteSeerX: 10.1.1.39.7717. 
15. Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. pp. 348; 559–561.ISBN 1-849-96720-2.