Contando o número de caminhos simples no gráfico não direcionado

18

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.

Ryan
fonte
2
Isso já foi solicitado no mathoverflow: mathoverflow.net/questions/18603/…
Listagem
5
Na verdade, a pergunta no mathoverflow era sobre encontrar todos os caminhos e não contá-los. Encontrá-los pode ser muito mais difícil.
amigos estão dizendo sobre dtcib
1
Além das referências dadas nas respostas, uma observação trivial é que, se se pode contar o número de caminhos de comprimento , pode-se responder à questão da existência de um caminho hamiltoniano. Então, provavelmente não é P.n1
Saeed

Respostas:

20

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 .kf(k)nk/2+O(1)O(nk)

Andreas Björklund
fonte
18

É # 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áficost ". 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.

David Richerby
fonte
4
O artigo de Roberts e Kroese parece não dar garantias de aproximação. Existe um PTAS conhecido por esse problema?
Sasho Nikolov
3
@SashoNikolov, parece improvável que exista algum algoritmo de aproximação razoável. Dado obtenha G de G substituindo cada nó por um clique do tamanho N = n c onde n = | V | e c 1 . Para cada caminho simples de comprimento em G há aproximadamente ( N ! ) S - t caminho hamiltoniano, haverá pelo menos ( NG=(V,E)GGN=ncn=|V|c1G caminhos em G . Então, se G tem um(N!)GGst ou mais simplescaminhos s - t em G e, no máximo, algo como ( n - 1 ) ! ( N ! ) N - 1 caminhossimples s - t . Portanto, deve ser difícil aproximar-se dentro de um fator de cerca de N ! 1 ! .(N!)nstG(n1)!(N!)n1stN!/(n1)!nc1!
Neal Young
6

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+δ)kO(2O(k))

RB
fonte