Czy istnieje algorytm do skutecznego utrzymywania informacji o połączeniach dla DAG w przypadku wstawiania / usuwania?

17

Biorąc pod uwagę ukierunkowany wykres acykliczny, G(V,E) , czy można skutecznie obsługiwać następujące operacje?

  • : Określa, czy w G istnieje ścieżkaod węzła a do węzła bisConnected(G,a,b)Gab
  • : Dodaje krawędź od a do b na wykresie Glink(G,a,b)abG
  • : Usuwa krawędź od a do b w Gunlink(G,a,b)abG
  • : Dodaje wierzchołek do Gadd(G,a)
  • : Usuwa wierzchołek z Gremove(G,a)

Kilka uwag:

  • Gdybyśmy niedozwolone , wydaje się, że to będzie łatwe do utrzymania informacji więzi, wykorzystując strukturę typu danych rozłącznego-set.unlink
  • Oczywiście może być realizowane za pomocą głębokości lub przeszukiwanie wszerz, stosując wskaźnik naiwne reprezentacji opartej na wykresie. Ale to jest nieefektywne.isConnected

Mam nadzieję na zamortyzowany stały lub logarytmiczny czas dla wszystkich trzech operacji. czy to możliwe?

Justin Kilpatrick
źródło
3
Powiązane: Pytano wcześniej o wersję przekierowanego wykresu. Czy istnieje algorytm online do śledzenia komponentów na zmieniającym się niekierowanym wykresie?
Tsuyoshi Ito
1
Czy możesz wyjaśnić, jak rozwiązać prostszy przypadek (bez odłączenia) przy użyciu struktury danych typu rozłącznego?
jbapple
@Tsuyoshi - linki do tego pytania wyglądają interesująco, teraz na nie patrzę.
Justin Kilpatrick
(1) Szukasz algorytmu dynamicznego wykresu dla ukierunkowanej osiągalności z zastrzeżeniem, że wykres jest DAG. Jeśli się nie mylę, osiągalność kierowana dynamicznie jest znacznie trudniejsza niż bezkierunkowy odpowiednik, ale tutaj właściwość DAG może pomóc. (2) Czy removeusuwa również krawędzie zdarzeń? Jeśli tak, wymaganie od tej operacji czasu O (log n) może być zbyt duże, aby mieć nadzieję….
Tsuyoshi Ito

Odpowiedzi:

19

Opisany przez ciebie problem dotyczy w pełni dynamicznej osiągalności DAG (zwanej również w pełni dynamicznym przechodzeniem przechodzenia na DAG). Nazywa się to w pełni dynamicznym, ponieważ ludzie badają również wersje, w których możliwe są tylko usunięcia (wtedy nazywa się to malejącą osiągalnością) i gdzie możliwe są tylko wstawienia (nazywane przyrostową osiągalnością).

Istnieje kilka kompromisów między czasem aktualizacji a czasem zapytania. Niech będzie liczbą krawędzi, a n liczbą wierzchołków. W przypadku DAG Demetrescu i Italiano (FOCS'00) podali losową strukturę danych, która obsługuje aktualizacje (wstawianie lub usuwanie krawędzi) w czasie O ( n 1,58 ) i zapytania o osiągalność w czasie O ( n 0,58 ) (obsługiwane są również wstawiania / usuwanie węzłów , w czasie O (1)); wynik ten został rozszerzony przez Sankowskiego (FOCS'04) do pracy dla ogólnych grafów kierowanych. Również w przypadku DAG Roditty (SODA'03) wykazał, że można zachować macierz przechodniego zamknięcia w całkowitym czasie O ( m n + I · n 2 + D ), gdziemnn1.58n0.58mn+I·n2+D to liczba wstawień, D liczba usunięć i oczywiście czas zapytania wynosi O ( 1 ).ID1

W przypadku grafów skierowanych ogólnie znane są następujące czasy (aktualizacja, zapytanie): (O ( ), O (1)) (Demetrescu i Italiano FOCS'00 (amortyzowane), Sankowski FOCS'04 (najgorszy przypadek)), ( O ( m n2 ),O(mn )) (Roditty, Zwick FOCS'02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC'04), (O (n 1,58 ), O (n 0,58 )) i (O (n 1.495 ), O (n 1.495 )) Sankowskiego (FOCS'04).O(nm+nlognnn1.58n0.58n1.495n1.495

Uzyskiwanie polilogarytmicznego czasu zapytania bez nadmiernego wydłużania czasu aktualizacji jest głównym otwartym problemem, nawet dla DAG.

dziewice
źródło
1
Dziękuję za Twoją odpowiedź. Chociaż muszę powiedzieć, że jestem rozczarowany, jak słabe są te granice. :(
Justin Kilpatrick
1
Powiązane pytanie: czy możesz wskazać mi odniesienia do prostszych problemów, przyrostowej dostępności i malejącej dostępności dla DAG?
Justin Kilpatrick
To nie wygląda na lepsze niż naiwne podejście DFS (O(1),O(n^2))lub (O(m),O(n+m)).
Thomas Ahle,
4

Myślę, że najlepsze dotychczasowe wyniki zostały omówione w „Zachowując dynamiczne macierze dla w pełni dynamicznego zamknięcia przechodniego” . W artykule omówiono algorytm losowy z czasem zapytania i czasem aktualizacji O ( n 1,58 ) .O(n0.58)O(n1.58)

(Dotyczy to tylko pierwszej wersji pytania, z linki unlinkbez addi remove.)

jbapple
źródło
The bounds are build on Strassen's algorithm though, so the constant is huge.
Thomas Ahle