Zliczanie liczby prostych ścieżek na nieukierowanym wykresie

18

W jaki sposób mogę ustalić liczbę unikalnych prostych ścieżek na niekierowanym wykresie? Albo dla określonej długości, albo w zakresie dopuszczalnych długości.

Przypomnij sobie, że prosta ścieżka to ścieżka bez cykli, więc mówię o policzeniu liczby ścieżek bez cyklu.

graph-theory co.combinatorics counting-complexity

— Ryan
źródło

2

Pytanie zostało już zadane na stronie mathoverflow: mathoverflow.net/questions/18603/…

— Listing

5

W rzeczywistości pytanie w matematycznym przepływie dotyczyło znalezienia wszystkich ścieżek, a nie ich liczenia. Ich znalezienie może być znacznie trudniejsze.

— DCTLib,

1

Oprócz odniesień podanych w odpowiedziach, jedną trywialną obserwacją jest to, że jeśli można policzyć liczbę ścieżek o długości wówczas można odpowiedzieć na pytanie o istnienie ścieżki hamiltonowskiej. Najprawdopodobniej nie jest to P.

n - 1

$n-1$

— Saeed

20

Istnieje kilka algorytmów, które liczą proste ścieżki długości w czasie , który jest o wiele lepszy niż czas brutalnej siły ( ). Patrz np. Vassilevska i Williams, 2009 . $k$ $f(k)n^{k/2+O(1)}$ $O(n^k)$

— Andreas Björklund
źródło

18

Jest to # P-complete (Valiant, 1979), więc prawdopodobnie nie zrobisz nic lepszego niż brutalna siła, jeśli chcesz dokładnej odpowiedzi. Przybliżenia omawia Roberts i Kroese (2007).

B. Roberts i DP Kroese, " Szacowanie liczby ścieżek - na wykresie $s$ $t$ ". Journal of Graph Algorytmy i aplikacje , 11 (1): 195–214, 2007.

LG Valiant, „ Złożoność problemów związanych z wyliczaniem i niezawodnością ”. SIAM Journal on Computing 8 (3): 410-421, 1979.

— David Richerby
źródło

4

Dokument Robertsa i Kroese'a nie wydaje się gwarantować przybliżenia. Czy znany jest PTAS dla tego problemu?

— Sasho Nikolov,

3

@SashoNikolov, wydaje się mało prawdopodobne, aby istniał jakiś rozsądny algorytm aproksymacyjny. Biorąc pod uwagę

uzyskaj

z

, zastępując każdy węzeł kliką o rozmiarze

gdzie

oraz

. Dla każdej prostej ścieżki długości

w

istnieją z grubsza

ścieżki w

. Więc jeśli

ma

G = (V, E)

$G=(V,E)$

G^{'}

$G'$

G

$G$

N = n^{c}

$N=n^c$

n = | V |

$n=|V|$

c ≫ 1

$c\gg 1$

ℓ

$\ell$

G

$G$

(N!)^{ℓ}

$(N!)^\ell$

G^{'}

$G'$

G

$G$

ścieżka Hamiltona, będzie co najmniej

lub tak prosteścieżki

w

, a w przeciwnym razie co najwyżej coś takiego jak

prosteścieżki

. Tak więc przybliżenie w granicach około

powinno być trudne

s - t

$s-t$

(N!)^{n}

$(N!)^{n}$

s - t

$s-t$

G^{'}

$G'$

(n - 1)! (N!)^{n - 1}

$(n-1)!(N!)^{n-1}$

s - t

$s-t$

.

N! / (n - 1)! ≫ n^{c - 1}!

$N!/(n-1)! \gg n^{c-1}!$

— Neal Young

6

Chciałbym dodać inny algorytm aproksymacyjny, sparametryzowany: dla ustalonego (lub bardziej precyzyjnie $\delta>0$ ), można obliczyćw-approximation liczby prostych odcinków, w obu nieukierunkowane lub skierowanej wykresie o długościw czasie. $\delta =\Omega(\frac{1}{poly(k)})$ $(1+\delta)$ $k$ $O^*(2^{O(k)})$

— RB
źródło