Approximation pour compter le nombre de chemins

On m'a dit qu'il existe de bons algorithmes de temps polynomiaux pour approximer le nombre de chemins simples dans un graphe orienté d'un sommet de départ donné à un sommet de fin donné . Quelqu'un connaît-il une bonne référence à ce sujet? $s$ $t$

Contexte: compter le nombre exact de chemins dans un graphique général est # P-complet mais il peut exister des approximations polynomiales temporelles pour le problème. Je suis particulièrement intéressé par les approximations aléatoires.

Merci d'avance.

ds.algorithms reference-request graph-algorithms approximation-algorithms counting-complexity bbejot
la source

J'ai eu le même problème à résoudre en utilisant Random Walk.

@bbejot: Voir À quel point est-il difficile de compter le nombre de chemins simples entre deux nœuds dans un graphique dirigé? La seule réponse, par Jmad, fournit un lien vers un article qui fournit en effet une approximation aléatoire

Carlos Linares López

Réponses:

Ce problème devrait être NP-difficile en réduisant la longueur maximale des chemins st.

$k$ $C_{\ell}$ $\ell$ $k^\ell C_{\ell}$ $k$ $C_{\ell_{max}}=1$

Heng Guo
la source