Eu tenho um gráfico direcionado e meu problema é enumerar todos osmínimo (ciclos que não podem ser construídos como a união de outros ciclos) ciclos dirigidos deste gráfico. Isso é diferente do que o algoritmo Tarjan gera. Por exemplo, para o gráfico direcionado emesta página da wikipediaEu gostaria de obter c <-> d e d <-> h como dois ciclos direcionados separados.

Eu não sei se esse problema é polinomial ou não. Corri um artigo "Enumerando Minimal Dicuts e Subgrafos Fortemente Conectados" que parece concluir que esse problema é polinomial incremental (não sei o que isso significa), mas não consigo extrair um algoritmo para este artigo. Eu também não tenho certeza se um componente mínimo fortemente conectado é equivalente a um ciclo mínimo como eu o defino.

Alguém sabe a resposta para este problema?

Desde já, obrigado!!!