Encontrando o número de ciclos de comprimento

9

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 Gf(k)n3GkkG

Kumar
fonte

Respostas:

11

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.kGkkO(VE)O(VωregistroV)kk

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 .3k7kO(Vω)ω<2,367kk3


[1] Flum, Jörg e Martin Grohe. "A complexidade parametrizada da contagem de problemas." Jornal SIAM sobre Computação 33.4 (2004): 892-922.

[2] Alon, Noga, Raphael Yuster e Uri Zwick. "Encontrar e contar determinados ciclos de duração." Algorithmica 17,3 (1997): 209-223.

Juho
fonte
10

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.(1+ϵ)

Michael Lampis
fonte
8

kf(k)nk/2+3

Andreas Björklund
fonte