Conjunto de arcos de realimentação: diferenças entre revisões

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 dirigidodirecionado (GAD). Uma maneira de fazer isso é simplesmente retirar arestas do grafo para retirarremover 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.

SãoEstreitamente estreitamenterelacionado relacionadas comé o conjunto de vértices de realimentação, que é um conjunto de vértices que contemcontém ao menos um vértice de cada ciclo no grafo dirigidodirecionado, 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 sãoforem invertidas ao invés de removidas, ondeentã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 tantastão poucas arestas quanto o 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.

Como um simples 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:

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 qualquer umnenhum dos três itens, e como este grafo é cíclico, você não é pode obter qualquer umnenhum deles também.

No entanto, suponha que você ofereceofereç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.

Tal como no exemplo acima, há geralmente um custo associado com a remoção de uma aresta. Por esta razão, nós gostaríamos de remover tantastã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|NP-Difícil]] chamado de conjunto de arcos de realimentação mínimo ou problema do subgrafo acíclico máximo.

Este problema é particularmente difícil no [[grafo k-aresta-conexo|<nowiki/>]][[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 Karp|Richard M. Karp]], provados atravésa partir da redução da [[Cobertura de vértices (teoria dos grafos)|cobertura de vértices]].

Apesar de serEmbora NP-completo, o conjunto de arcos de realimentação eé um [[:en:Parameterized_complexity#FPT|ftp]]: existe um algoritmo para solucionasolucioná-lo o qual ocujo tempo tede execução é polinomialum polinômio fixado no tamanho do grafo de entrada (independentemente do numeronúmero de arestas no conjunto) mas exponencial no numeronú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 completude]]-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 encontramencontra um conjunto de arestas no máximo c vezes maior que o resultado ótimo. A partir de <span>2006</span><sup class="plainlinks noprint asof-tag update" style="display:none;">[//en.wikipedia.org/w/index.php?title=Feedback_arc_set&action=edit &#x5B;update&#x5D;][//en.wikipedia.org/w/index.php?title=Feedback_arc_set&action=edit]</sup>, o maior valor de c para talo qual um resultado improvávelde 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 numeronúmero de arestas em um subgrafo acíclico a, uma aproximação um pouco melhor que 1/2 é possível.

Se os dígrafos de entrada são restritos paraa seremtorneios desafiadores(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 [[:en:Polynomial-time_approximation_scheme|esquema de aproximação de tempo polinomial]], Ee eleisso ainda é valido para a versão ponderada do problema. Um algoritmo de parâmetro fixo subexponencial para ponderar rapidamente FAST foi dado por {{Harvtxt|Karpinski|Schudy|2010}}.

Por outro lado, se as arestas são uninão-direcionadas, o problema de remover arestas para fazertornar o grafo livre de ciclo liver é equivalente a encontrar uma [[Árvore de extensão mínima|Arvore de extensão mínima]] , a qual pode ser feita facilmente em tempo polinomial.

Vários algoritmos de aproximação para o problema temtêm sido desenvolvidos. Um algoritmo particularmente simples é descrito a seguir:

* CorrigirFixe uma permutação arbitrariaarbitrária dos vértices, ou seja, rotularotule-losos de 1 a {{Mvar|n}}.