Aproximação para contar o número de caminhos

Foi-me dito que existem bons algoritmos de tempo polinomial para aproximar o número de caminhos simples em um gráfico direcionado, desde o vértice inicial dado até o vértice final dado $s$ $t$ . Alguém sabe de uma boa referência sobre este assunto?

Antecedentes: contar o número exato de caminhos em um gráfico geral é # P-completo, mas pode haver aproximações de tempo polinomial para o problema. Estou especialmente interessado em aproximações aleatórias.

Desde já, obrigado.

ds.algorithms reference-request graph-algorithms approximation-algorithms counting-complexity bbejot
fonte

Tive o mesmo problema e resolvi usando o Random Walk.

@bbejot: Veja Quão difícil é contar o número de caminhos simples entre dois nós em um gráfico direcionado? A única resposta, por Jmad, fornece um link para um artigo que fornece de fato uma aproximação aleatória

Carlos Linares López

Respostas:

Esse problema deve ser difícil para NP, reduzindo o comprimento máximo dos caminhos st.

A redução simplesmente substitui todas as arestas por, digamos, $k$ arestas paralelas. (Se você não se sentir confortável com um gráfico múltiplo, substitua cada aresta por um caminho de comprimento 2.) O efeito disso é que o número $C_{\ell}$ de caminhos de comprimento $\ell$ se torna $k^\ell C_{\ell}$ . Assim, se $k$ for adequadamente grande, o termo correspondente aos caminhos mais longos no gráfico original dominará todo o resto (mesmo que $C_{\ell_{max}}=1$ ). A partir daí, você pode recuperar facilmente o comprimento do caminho mais longo.

Heng Guo
fonte