Tengo un gráfico dirigido y mi problema es enumerar todos losmínimo (ciclos que no se pueden construir como la unión de otros ciclos) ciclos dirigidos de este gráfico. Esto es diferente de lo que produce el algoritmo de Tarjan. Por ejemplo, para el gráfico dirigido aesta pagina de wikipedia, Me gustaría obtener c <-> d y d <-> h como dos ciclos dirigidos separados.

No lo hago si este problema es polinomial o no. Me encontré con un documento "Enumerando las representaciones mínimas y los subgrafos fuertemente conectados" que parece concluir que este problema es un polinomio incremental (no sé lo que significa), pero no puedo extraer un algoritmo para este artículo. Tampoco estoy seguro de si un componente mínimo fuertemente conectado es equivalente a un ciclo mínimo como lo defino.

¿Alguien sabe la respuesta a este problema?

¡¡¡Gracias por adelantado!!!