Temos o algoritmo para determinar se um gráfico tem um ciclo de comprimento exatamente . Como podemos descobrir quantas dessas motocicletas estão presentes em usando o mesmo ou qualquer outro algoritmo. G k k G
Temos o algoritmo para determinar se um gráfico tem um ciclo de comprimento exatamente . Como podemos descobrir quantas dessas motocicletas estão presentes em usando o mesmo ou qualquer outro algoritmo. G k k G
Quando faz parte da entrada, o problema de decidir se G contém um ciclo simples de comprimento k é NP-completo. Para cada k fixo , o problema pode ser resolvido no tempo O ( V E ) ou O ( V ω log V ) . Flum e Grohe [1] mostraram que a contagem de ciclos e caminhos de comprimento k em gráficos direcionados e não-direcionados, parametrizados por k , é #W [1] completo.
Para , pode-se contar as k- motocicletas no tempo O ( V ω ) , onde ω < 2,337 é o expoente da multiplicação da matriz. Este é o resultado de Alon, Yuster e Zwick [2]. O artigo também contém métodos para encontrar ciclos simples de comprimento exatamente k , onde k ≥ 3 .
Como Juho apontou, o problema é conhecido por ser #W [1] concluído pelo trabalho de Flum e Grohe. No entanto, existe um esquema de aproximação aleatória que é executado no tempo do FPT e retorna uma estimativa que é um fator distante da solução correta com alta probabilidade. Consulte "Algoritmos de aproximação para alguns problemas de contagem parametrizada", de Arvind e Raman, ISAAC 2002.