Podgraf zawierający wszystkie węzły i krawędzie, które są częścią prostych ścieżek st o ograniczonej długości na niekierowanym wykresie

Całkiem podobne do mojego wcześniejszego pytania . Tym razem jednak wykres nie jest przekierowany.

Dany

Nieukierunkowane wykres $G$ bez wielu krawędzie lub pętli
Źródło wierzchołek $s$ ,
Docelowy wierzchołek $t$ ,
Maksymalna długość ścieżki $l$ ,

Szukam $G'$ - podgraf $G$ który zawiera dowolny wierzchołek i dowolną krawędź w $G$ (i tylko te), które są częścią co najmniej jednej prostej ścieżki od $s$ do $t$ o długości $\leq l$ .

Uwagi:

Nie muszę wyliczać ścieżek.
Szukam wydajnego algorytmu (zarówno czasu, jak i pamięci), ponieważ muszę go wykonać na bardzo dużych wykresach (10 ^ 8 wierzchołków, 10 ^ 9 krawędzi).

ds.algorithms graph-algorithms shortest-path

— Lior Kogan
źródło

Sprawdź to. Znaleziono ten artykuł, który wydaje się robić podobną redukcję przepływu kosztów minimalnych, ale wykorzystuje specjalne cechy sieci, aby rozwiązać go szybciej niż ogólne algorytmy MCF.

— RB

Odpowiedzi:

Cóż, problem jest w po wszystkim. Zachowam poprzednią odpowiedź, ponieważ działa ona również w przypadku skierowanym (którym jest NPC, jak odpowiedziano na drugie pytanie) i pokazuje, że w odniesieniu do . $P$ $FPT$ $l$

W przypadku nieukierunkowanym jest on rozwiązywalny, deterministycznie poprzez minimalny przepływ kosztów (może to nie działać na skalach, o których mowa w pytaniu, ale jest lepszy niż algorytm wykładniczy.

Poniższa procedura zadecyduje, czy część zbocza powinna być częścią wykresu wyjściowego. Aby rozwiązać pierwotny problem, po prostu zapętl wszystkie krawędzie. $e=(u,v)\in E$

Aby utworzyć sieć przepływu, wykonaj następujące czynności:

Krok 1: Rozwiń aby mieć wierzchołek i zamień na krawędzie (są one skierowane jako część sieci przepływowej), ustaw ich koszt na 0. $e$ $x_e$ $e$ $(u,x_e),$ $(x_e,u),(v,x_e),(x_e,v)$

Krok 2: zamień każdy wierzchołek , z wyjątkiem na dwa wierzchołki i , i dodaj krawędź . Ustaw koszt tych krawędzi na 1. $t$ $x_e$ $t^-$ $t^+$ $(t^-,t^+)$

Krok 3: Zastąp każdą krawędź krawędziami . Ustaw koszt tych krawędzi na 0. $\{a,b\}\in E$ $(a^+,b^-),(b^+,a^-)$

Krok 4: Dodaj nowy wierzchołek i dodaj krawędzie z kosztem 0. $y_e$ $(s,y_e),(t,y_e)$

Krok 5: ustaw wszystkie pojemności na 1.

Teraz uruchom algorytm przepływu kosztu minimalnego, szukając przepływu o wartości 2 od do . $x_e$ $y_e$

Analiza:

$x_e$ $y_e$ $x_e\leadsto s\to y_e$ $x_e\leadsto t\to y_e$
Ścieżki są rozłączne, ponieważ dla każdego wierzchołka jest tylko 1 pojemność w łuku . $t$ $(t^-,t^+)$
Zwrócone ścieżki to dwie ścieżki, których suma odległości jest minimalna, a to także koszt znalezionego przepływu. To pozwala nam dodać do wykresu wyjściowego lub usunąć w inny sposób. $e$

— RB
źródło

Łatwiej jest zrozumieć argument w powyższej odpowiedzi, usuwając redukcję do ukierunkowanego przepływu. Istnieje prosta ścieżka od do zawierająca węzeł iff, istnieje ścieżka od do oraz ścieżka od do tak że i są węzłami rozłącznymi, z wyjątkiem . To zasadniczo wykorzystuje bezkierunkowość. Można to sprawdzić za pomocą przepływu, a wersję kosztową można również wykonać za pomocą przepływu minimalnego kosztu. Można sprawdzić, czy istnieje prosta ścieżka od do zawierająca

s

$s$

t

$t$

v

$v$

P

$P$

v

$v$

s

$s$

Q

$Q$

v

$v$

t

$t$

P

$P$

Q

$Q$

v

$v$

s

$s$

t

$t$

e

$e$ wprowadzając węzeł w środku .

e

$e$

— Chandra Chekuri

@ChandraChekuri - to prawda, ale pamiętaj, że jeśli problem nie ma ograniczenia długości, istnieje znacznie prostszy algorytm do podjęcia decyzji - patrz tutaj

— RB

Jasne, wiem też o tym rozwiązaniu - koncepcyjnie dobrze jest rozumieć komponenty połączone ze sobą za pomocą rozłącznych ścieżek, chociaż można znaleźć wycięte wierzchołki i połączone komponenty bezpośrednio przez DFS.

— Chandra Chekuri

@RB: Dziękuję. Sugerowany algorytm może być skuteczny, gdy l jest względnie duże, ale prawdopodobnie jest nieoptymalne dla względnie małych wartości l. Chyba mogę najpierw przyciąć G, usuwając wierzchołek dalej niż podłoga (l / 2) zs i sufit (l / 2) zt.

— Lior Kogan

Spróbuj dostosować kolejny algorytm najkrótszej ścieżki (zwany również algorytmem Surballe'a w przypadku 2 ścieżek, które są tu interesujące). Chcesz znaleźć najkrótsze 2 ścieżki od (lepiej nazwać to zamiast ponieważ jest takie samo dla wszystkich krawędzi) do każdego . Myślę, że można to zrobić skutecznie, najpierw obliczając drzewo najkrótszej ścieżki od a następnie ostrożnie wdrażając obliczenia drugiej ścieżki.

y

$y$

y

$y$

y_{e}

$y_e$

x_{e}

$x_e$

y

$y$

— Chandra Chekuri

Oto zła odpowiedź: generuje niektóre wierzchołki, które są częścią nieprostych ścieżek od do i które nie są częścią żadnej prostej ścieżki od do długości . Odpowiedź może nadal dotyczyć wniosku osoby pytającej, więc zostawiam ją tutaj. $s$ $t$ $s$ $t$ $\le \ell$

Oto algorytm działający w czasie (i faktycznie jest szybszy niż ten, gdy jest mały). $O(|V|+|E|)$ $\ell$

Algorytm uruchamia wyszukiwanie BFS od które kończy się na głębokości . Ten BFS daje zestaw wszystkich wierzchołków osiągalnych z ze ścieżką o długości co najwyżej , a także oblicza odległości dla każdego . Następnie zrobiłbym to samo i zestaw i odległości od . Wreszcie wierzchołki, których szukasz, to dokładnie . Krawędzie są dokładnie tymi krawędziami w $s$ $\ell$ $V_s$ $s$ $\ell$ $dist(s,v)$ $v \in V_s$ $t$ $V_t$ $t$ $V_{solution}=\{ v : v \in V_s \cap V_t, dist(s,v)+dist(t,v) \le \ell \}$ ( ). $E[V_{solution}]$ $=(v,u) \in E : u,v \in V_{solution}$

Czas działania tego algorytmu jest z pewnością ponieważ robi on tylko dwa BFS. Ale czas działania jest w rzeczywistości który będzie znacznie mniejszy niż rozmiar wykresu, gdy promieniowe sąsiedztwa i są małe. $O(|V|+|E|)$ $O(|V_s| + |V_t| + |E[V_s]|+|E[V_t]|)$ $\ell$ $s$ $t$

Edycja: prawdopodobnie w praktyce jest nieco szybszy algorytm, który wykonuje BFS z głębokości i tylko zamiast . To odkrywa wszystkie ścieżki, a następnie przy odrobinie księgowości można znaleźć wszystkie wierzchołki. Skraca to czas działania o pierwiastek kwadratowy w przypadku dużego losowo wyglądającego wykresu, gdy jest małe. $s$ $t$ $\ell/2$ $\ell$ $\ell$

— pierożek Mobiusa
źródło

To nie zmusza ścieżki do bycia prostym. Rozważ prosty wykres ścieżki

. Zwrócisz jako część wyniku, chociaż nie ma prostej ścieżki st, która przechodzi przez ...

t - u - s - v - x

$t-u-s-v-x$

l = 4

$l=4$

v

$v$

v

$v$

— RB

Dzięki za korektę @RB. Zredagowałem swoją odpowiedź, aby zauważyć, że jest zła.

— pierożek Mobius

Jest to zamierzone jako komentarz, ale jest zbyt długi, aby opublikować komentarz.

Możesz również być zainteresowany kluczami graficznymi lub emulatorami do swoich celów. Klucz grafu jest subgraph z kilkoma krawędzi, ale w przybliżeniu zachowana odległości. Emulator to wykres którego krawędzie mogą być ważone. $G = (V, E)$ $H = (V, E')$ $H = (V, E', w)$

Najlepszy wynik dla kluczy to krawędzi i błąd addytywny +6 w szacunkach odległości na wykresie. Najlepszy wynik dla emulatorów to krawędzie i błąd addytywny +4. Nie wiadomo też, czy możemy pokonać , nawet jeśli błąd może być polilogarytmiczny. $O(n^{4/3})$ $O(n^{4/3})$ $O(n^{4/3})$

Jeśli to wydaje się przydatne, mogę spróbować wykopać odpowiednie konstrukcje dla ciebie.

— GMB
źródło