Encontrar el número de ciclos de longitud

Tenemos un algoritmo de tiempo para determinar si un gráfico G tiene un ciclo de longitud exactamente k . ¿Cómo podemos encontrar cuántos k- ciclos están presentes en G usando el mismo algoritmo o cualquier otro?$f(k) n^3$$G$$k$$k$$G$

Cuando es parte de la entrada, el problema de decidir si G contiene un ciclo simple de longitud k es NP completo. Para cada k fijo , el problema puede resolverse en tiempo O ( V E ) u O ( V ω log V ) . Flum y Grohe [1] mostraron que contar ciclos y trayectorias de longitud k en gráficos dirigidos y no dirigidos, parametrizados por k , es #W [1] -completo.$k$$G$$k$$k$$O(VE)$$O(V^\omega \log V)$$k$$k$

$3 \leq k \leq 7$$k$$O(V^\omega)$$\omega < 2.376$$k$$k \geq 3$

[1] Flum, Jörg y Martin Grohe. "La complejidad parametrizada de los problemas de conteo". SIAM Journal on Computing 33.4 (2004): 892-922.

[2] Alon, Noga, Raphael Yuster y Uri Zwick. "Encontrar y contar ciclos de longitud dados". Algorithmica 17.3 (1997): 209-223.

$(1+\epsilon)$

$k$$f(k)n^{\lceil k/2 \rceil+3}$