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?
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ę.
ds.algorithms
reference-request
graph-algorithms
approximation-algorithms
counting-complexity
bbejot
źródło
źródło
Odpowiedzi:
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ę kℓCℓ . 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ℓmax=1 ). Stamtąd możesz łatwo odzyskać długość najdłuższej ścieżki st.
źródło