Przybliżenie do zliczania liczby prostych ścieżek

17

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?st

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ę.

bbejot
źródło
Miałem ten sam problem, który rozwiązałem za pomocą Random Walk.
2
@bbejot: Zobacz, jak trudno policzyć liczbę prostych ścieżek między dwoma węzłami na ukierunkowanym wykresie? Jedyną odpowiedzią autorstwa jmad jest link do artykułu, który zapewnia rzeczywiście losowe przybliżenie
Carlos Linares López

Odpowiedzi:

1

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 ścieżek o długości staje się kC . 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 Cmax=1 ). Stamtąd możesz łatwo odzyskać długość najdłuższej ścieżki st.

Heng Guo
źródło