Estou preso ao seguinte problema: Dado um dígrafo ponderado G, eu gostaria de construir o subgráfico mínimo de G que contém todos os ciclos negativos (simples) de G.

Eu sei como encontrar um ciclo negativo usando Bellman-Ford, e sei que o número de ciclos simples em um grafo direcionado é exponencial.

Uma maneira ingênua de abordar o problema seria simplesmente iterar todos os ciclos simples e escolher aqueles que são negativos, mas tenho a sensação de que pode haver um algoritmo de tempo polinomial. A maioria dos artigos que encontrei no Google foi sobre encontrar um ciclo negativo (e não todo).

Espero encontrar alguns especialistas aqui no stackoverflow que possam dar algumas dicas para uma solução de tempo polinomial, ou sugestões para provar que não podem ser resolvidos em tempo polinomial.

Muito obrigado antecipadamente!

Felicidades, Robert