Algoritmo de aproximação para conjunto de arco de realimentação

7

Dado um gráfico direcionado G=(V,A), um conjunto de arco de feedback é um conjunto de arcos cuja remoção deixa um gráfico acíclico. O problema é encontrar a cardinalidade mínima desse conjunto.

Eu quero descobrir se existe algum algoritmo de aproximação em torno desse problema.

algorithms graph-theory approximation amir079
fonte
11
O que você quer saber sobre esse problema? O problema de decisão correspondente é NP-completo.
Shaull 18/09/13
2
Em seguida, edite sua postagem e adicione detalhes sobre o que você está procurando e o que você já tentou. É provável que você obtenha mais respostas dessa maneira.
Shaull 18/09/2013
11
Se você está procurando um algoritmo de aproximação, tentou pesquisar no Google? Você encontrará bastante material.
Juho
@ Shaull existe um nome chique para o problema?
precisa saber é o seguinte
"Conjunto de comentários" é o nome correto. Fantasia o suficiente, eu acho.
Shaull 19/09/13

Respostas:

7

O compêndio on-line de problemas de NPO da Kann é um bom ponto de partida. Conjunto de arco de feedback (a "parte direcionada é redundante quando você usa" arco ") é:

  • APX-hard,
  • Aproximado dentro O(log⁡nlog⁡log⁡n) (Onde n é o número de vértices).

O problema também é de parâmetro fixo tratável 1 , portanto, pode fazer mais sentido resolver o problema exatamente, em vez de usar o que parece ser um algoritmo de aproximação ruim. (Ou, como Pål aponta abaixo, o tempo de execução é um pouco ... desagradável, talvez não.)

Notas

1 - publicação JACM , preprint de Razgon & Sullivan , Chen, Liu e preprint de Lu - o problema foi resolvido de forma independente e os resultados combinados para uma publicação

Luke Mathieson
fonte
Só porque existe um algoritmo FPT, não significa realmente que faz mais sentido resolver o problema exatamente. Especialmente quando o tempo de execução éΩ(n4k!). (Disclaimer: Eu não tenho nenhuma idéia do que o melhor tempo de corrida conhecido por FAS é!)
Pål GD
BTW, existe algo como a lista de Kann que seria mais atualizada? Parece que a última atualização é de 2000. Provavelmente não ...
Juho
Infelizmente, não conheço nenhum recurso semelhante. É um bom ponto de partida, mas se você falou sério, voltou aos métodos de pesquisa mais trabalhosos.
usar o seguinte texto