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.

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

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$

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