Como posso determinar o número de caminhos simples exclusivos em um gráfico não direcionado? Por um determinado comprimento ou por um intervalo de comprimentos aceitáveis.
Lembre-se de que um caminho simples é um caminho sem ciclos, então estou falando sobre contar o número de caminhos sem ciclo.
Respostas:
Existem vários algoritmos que contam os caminhos simples de comprimento no tempo f ( k ) n k / 2 + O ( 1 ) , o que é muito melhor do que a força bruta (tempo O ( n k ) ). Ver, por exemplo, Vassilevska e Williams, 2009 .k f(k)nk/2+O(1) O(nk)
fonte
É # P-complete (Valiant, 1979), então é improvável que você faça muito melhor que a força bruta, se quiser a resposta exata. Aproximações são discutidas por Roberts e Kroese (2007).
B. Roberts e DP Kroese, " Estimando o número de caminhos - t em um gráficos t ". Journal of Graph Algorithms and Applications , 11 (1): 195-214, 2007.
LG Valiant, " A complexidade dos problemas de enumeração e confiabilidade ". Jornal SIAM sobre Computação 8 (3): 410-421, 1979.
fonte
Eu gostaria de adicionar outro algoritmo de aproximação, um parametrizado: para um fixoδ>0 (ou mais precocemente, ), você pode calcularumaaproximação(1+δ)do número de caminhos simples, no gráfico não direcionado ou direcionado, do comprimentokno tempoO∗(2O(k)).δ=Ω(1poly(k)) (1+δ) k O∗(2O(k))
fonte