Obliczanie przejściowego zakończenia / wyroku istnienia ścieżki

Było kilka pytań ( 1 , 2 , 3 ) na temat przechodniego uzupełniania, które zmusiły mnie do zastanowienia się, czy coś takiego jest możliwe:

Załóżmy, że otrzymujemy wykres skierowany na dane wejściowe $G$ i chciałby odpowiedzieć na zapytania typu „$(u,v)\in G^+$? ”, tzn. pytając, czy istnieje krawędź między dwoma wierzchołkami w przechodnianym zakończeniu wykresu $G$? (równoważnie „jest ścieżka do$u$ do $v$ w $G$? ”).

Zakładaj po danym $G$ możesz uruchomić przetwarzanie wstępne na czas $f(n,m)$ a następnie wymagane na czas odpowiedzieć na pytania $g(n,m)$.

Oczywiście, jeśli $f=0$ (tzn. żadne przetwarzanie wstępne nie jest dozwolone), najlepiej możesz odpowiedzieć na zapytanie na czas $g(n)=\Omega(n+m)$. (uruchom DFS z$u$ do $v$ i zwróć true, jeśli istnieje ścieżka).

Innym trywialnym wynikiem jest to, że jeśli $f=\Omega(min\{n\cdot m,n^\omega\})$, możesz obliczyć zamknięcie przechodnie, a następnie odpowiedzieć na zapytania w $O(1)$.

Co powiesz na coś pośrodku? Powiedz, jeśli masz pozwolenie$f=n^2$ czas wstępnego przetwarzania, czy możesz odpowiadać na zapytania szybciej niż $O(m+n)$? Może to poprawić$O(n)$?

Inna odmiana to: załóżmy, że masz $poly(n,m)$ czas przygotowania, ale tylko $o(n^2)$ miejsca, czy można użyć przetwarzania wstępnego, aby odpowiadać na zapytania wydajniej niż $O(n+m)$?

Czy możemy ogólnie powiedzieć coś o $f,g$ kompromis, który pozwala odpowiadać na takie zapytania?

Nieco podobna struktura kompromisu jest rozważana w systemach GPS, w których utrzymywanie kompletnej tabeli routingu wszystkich par odległości między lokalizacjami jest niemożliwe, dlatego wykorzystuje ideę wyroczni odległości, która przechowuje tabelę częściową, ale pozwala na znaczne przyspieszenie zapytań w stosunku do obliczania odległości całej wykres (zwykle daje jedynie przybliżoną odległość między punktami).

Istnieją niewielkie wyrocznie osiągalności dla płaskich wykresów,

Mikkel Thorup: Kompaktowe wyrocznie dla osiągalności i przybliżonych odległości w płaskich digrafach . J. ACM 51 (6): 993-1024 (2004)

ale są „twarde” dla grafów ogólnych (nawet grafów rzadkich)

Mihai Patrascu: Ujednolicenie krajobrazu dolnych granic sondy komórkowej . SIAM J. Comput. 40 (3): 827–847 (2011 r.)

Niemniej jednak istnieje algorytm, który może obliczyć oznakowanie zbliżone do optymalnego

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Zapytania dotyczące zasięgu i odległości za pomocą etykiet 2-Hop . SIAM J. Comput. 32 (5): 1338–1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algorytmy optymalizacji etykiety piasty . ICALP 2013: 69–80

Opierając się na pracach Cohena i in. i inne, istnieje sporo badań stosowanych (społeczność baz danych) patrz np

Ruoming Jin, Guan Wang: Prosta, szybka i skalowalna baza danych Oracle . PVLDB 6 (14): 1978–1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: Szybkie i skalowalne zapytania dotyczące osiągalności na wykresach przez przycięte etykietowanie punktami orientacyjnymi i ścieżkami . CIKM 2013: 1601–1606

Odpowiem częściowo na twoje pytanie: wydaje się, że istnieją pewne powody, dla których taka konstrukcja może być trudna do uzyskania.

Załóżmy, że biorąc pod uwagę dowolny n-węzłowy wykres skierowany na krawędź m, możesz go wstępnie przetworzyć w czasie T (m, n), aby odpowiedzi na zapytania o osiągalność można było odpowiedzieć w czasie q (m, n). Następnie, na przykład, możesz znaleźć trójkąt na n-węźle grafu m-edge w$T(O(m),O(n))+n q(O(m),O(n))$czas. W związku z tym$T(m,n)=O(n^2)$ i $q(m,n)=O(n)$oznaczałoby przełomowy wynik. Działa najlepszy algorytm do wyszukiwania trójkątów$O(n^\omega)$ czas i nie jest jasne, czy $\omega=2$.

Aby zobaczyć redukcję, załóżmy, że chcemy znaleźć trójkąt na jakimś wykresie $G$. Zbuduj 4-warstwowy wykres na 4 zestawach$n$ węzły każdy $X,Y,Z,W$ gdzie każdy oryginalny węzeł $v$ w $G$ ma kopie $v_X,v_Y,v_Z,v_W$. Teraz dla każdej krawędzi$(u,v)$ w $G$ dodaj skierowane krawędzie $(u_X,v_Y),(u_Y,v_Z),(u_Z,v_W)$. To kończy wykres. Teraz wykonaj wstępne przetwarzanie w$T(O(m),O(n))$ czas i zapytaj o $v_X,v_W$ dla każdego $v$.

Prawdopodobnie przy odrobinie pracy można zmienić redukcję, aby wyświetlić również trójkąty na wykresie (obecnie wyświetla tylko węzły w trójkątach). Jeśli można to zrobić efektywnie, prawdopodobnie można uzyskać warunkową dolną granicę w oparciu o wymaganie 3SUM$n^{2+o(1)}$ również czas, wykorzystując wynik Patrascu z 2010 roku.