Przybliżenie do zliczania liczby prostych ścieżek

I powiedziano, że istnieją dobre wielomianowe algorytmy czasu dla zbliżenia liczbę prostych odcinków w skierowanej wykresie począwszy od danego wierzchołka do danego zakończony wierzchołek T . Czy ktoś zna dobre referencje na ten temat?$s$$t$

Tło: zliczanie dokładnej liczby ścieżek na ogólnym wykresie jest # P-pełne, ale mogą istnieć przybliżone wielomianowe czasy dla problemu. Szczególnie interesują mnie przypadkowe przybliżenia.

Z góry dziękuję.

Ten problem powinien być trudny do NP, ponieważ zmniejsza się od maksymalnej długości ścieżek st.

Redukcja po prostu zastępuje każdą krawędź, powiedzmy, $k$ równoległymi krawędziami. (Jeśli nie czujesz się komfortowo w przypadku wielu wykresów, zastąp każdą krawędź ścieżką o długości 2). Efektem tego jest to, że liczba $C_{\ell}$ ścieżek o długości $\ell$ staje się $k^\ell C_{\ell}$ . Zatem, jeśli $k$ jest odpowiednio duże, termin odpowiadający najdłuższym ścieżkom na oryginalnym wykresie zdominuje wszystko inne (nawet jeśli $C_{\ell_{max}}=1$ ). Stamtąd możesz łatwo odzyskać długość najdłuższej ścieżki st.