Kontrola przechodniości a zamknięcie przechodnie

9

Czy sprawdzenie przechodniości digrapha nie jest łatwiejsze niż (pod względem asymptotycznej złożoności) przyjęcie przejścia przechodniego digrapha? Czy znamy dolną granicę lepiej niż aby ustalić, czy digraf jest przechodni? $\Omega(n^2)$

graph-theory directed-acyclic-graph transitive-closure

— ekayaaslan
źródło

1

Przechowywanie całego zamknięcia przechodniego będzie kosztować dodatkowe miejsce. W przypadku niektórych wykresów powinieneś być w stanie przechwycić i skrócić kontrolę przechodniości bez powrotu do krawędzi. Patrz: Algorytm łączności równoległej , Y Shiloach, U Vishkin - Journal of Al Algorytmy, 1982

O (l o g n)

$O(log n)$

— Chad Brewbaker

1

Tutaj Siek ma uwagi dotyczące implementacji Boost Graph Library boost.org/doc/libs/1_54_0/libs/graph/doc/…

— Chad Brewbaker

2

Nie jestem pewien, co rozumiesz przez , ale dolna granica jest prosta - rozważ dla niektórych krawędzi . Każdy algorytm poprosi o sprawdzenie, czy dla wszystkich , w przeciwnym razie krawędź, o którą nie zapytał, może być tą brakującą. jest górną granicą, ponieważ jest to czas potrzebny do obliczenia zamknięcia przechodniego.

n

$n$

Ω (| V |^{2})

$\Omega(|V|^2)$

K_{n} ∖ {e}

$K_n \setminus \{e\}$

e

$e$

(u, v) \in E

$(u,v)\in E$

u, v \in V

$u,v\in V$

O (| V | \cdot | E |)

$O(|V|\cdot |E|)$

— RB

2

Rozważ skierowany wykres z wierzchołków: wierzchołki źródłowe , pośrednie wierzchołki które są bezpośrednimi następcami każdego , i zatapianie wierzchołków które są bezpośrednimi następcami każdego z nich . Digraf jest przechodni, jeśli każdy z łuków jest obecny na wykresie. Wymaga to sprawdzenia krawędzi. Z drugiej strony znalezienie zamknięcia przechodniego można wykonać w czasie , gdzie jest wykładnikiem mnożenia macierzy. Są to najbardziej znane granice.

n = 3 k

$n = 3k$

s_{1}, \dots, s_{k}

$s_1,\dots,s_k$

t_{1}, \dots, t_{k}

$t_1,\dots,t_k$

s_{i}

$s_i$

u_{1}, \dots, u_{k}

$u_1,\dots,u_k$

t_{i}

$t_i$

(s_{i}, u_{j})

$(s_i,u_j)$

k^{2} = (n / 3)^{2} = Ω (n^{2})

$k^2 = (n/3)^2 = \Omega(n^2)$

O (n^{ω})

$O(n^\omega)$

ω < 2.373

$\omega < 2.373$

— András Salamon,

Czy Twój DAG może mieć jakąś dodatkową strukturę, czy chcesz mieć w pełni ogólne wyniki?

— Niel de Beaudrap

9

Poniżej pokażę: jeśli masz O ( $n^{3-\varepsilon}$ ) algorytm czasowy do sprawdzania, czy wykres jest przechodni dla dowolnego $\varepsilon>0$ , masz O ( $n^{3-\varepsilon}$ ) algorytm czasowy do wykrywania trójkąta w $n$ wykres węzłów, a zatem (na papierze z FOCS'10 ) miałbyś O ( $n^{3-\varepsilon/3}$ ) algorytm czasowy do pomnożenia dwóch wartości logicznych $n\times n$ macierze, a zatem w wyniku Fischera i Meyera z lat 70. , oznacza to również O ( $n^{3-\varepsilon/3}$ ) algorytm czasowy zamknięcia przechodniego.

Załóżmy, że chcesz wykryć trójkąt w $n$ węzeł $G$ . Możemy teraz utworzyć następujący wykres $H$ . $H$ jest trójstronny z partycjami $I,J,K$ na $n$ węzły każdy. Tutaj każdy węzeł $x$ z $G$ ma kopie $x_I,x_J,x_K$ W części . Dla każdej krawędzi z $I,J,K$ $(u,v)$ $G$ dodaj skierowane krawędzie $(u_I,v_J)$ i $(u_J,v_K)$ . Dla każdego nonedge $(u,v)$ z $G$ dodaj skierowaną krawędź $(u_I,v_K)$ .

Po pierwsze, jeśli $G$ zawiera trójkąt $u,v,w$ , następnie $H$ nie jest przechodnie. Wynika to z krawędzi $(u_I,v_J),(v_J,w_K)$ są w $H$ ale $(u_I,w_K)$ nie jest. Po drugie, jeśli $H$ nie jest przechodnie, więc musi istnieć jakaś ukierunkowana ścieżka z jakiegoś węzła $s$ do jakiegoś węzła $t$ w $H$ takie, że $(s,t)$ nie jest ukierunkowaną krawędzią $H$ . Najdłuższe ścieżki w $H$ mieć $2$ krawędzie, więc każda taka ścieżka musi mieć formę $(u_I,v_J),(v_J,w_K)$ i $(u_I,w_K)$ nie jest w $H$ , W związku z tym $u,v,w$ uformować trójkąt w $G$ .

— dziewice
źródło

1

Znalezienie zamknięcia przechodniego jest zasadniczo takie samo jak mnożenie macierzy. Pytanie brzmi, czy wykładnik w dolnej granicy można podnieść z 2, czy wykładnik w górnej granicy można obniżyć z 2,373. Wykazany przez ciebie ciąg rozumowania pokazuje, że nawet optymalne

O (n^{2})

$O(n^2)$ algorytm sprawdzania przechodniości dawałby tylko

O (n^{2.667})

$O(n^{2.667})$ algorytm czasowy dla przejścia przechodniego - ale już mamy

O (n^{2.373})

$O(n^{2.373})$ algorytm czasowy.

— András Salamon

Chodzi o to, że istnieją redukcje czarnej skrzynki. The O (

n^{2.373}

$n^{2.373}$ ) algorytm czasu jest daleki od praktycznego. Praktyczny algorytm sprawdzania przechodniości, który działa w czasie subububowym, przy powyższych redukcjach, sugeruje jednak również praktyczny algorytm dla BMM, a tym samym zamykanie przechodnie. Ponadto, nawet jeśli nie przejmujesz się praktycznymi algorytmami, jest całkiem możliwe, że utrata wykładnika z papieru FOCS'10 nie jest konieczna, a wykrywanie trójkątów jest prawdopodobnie równoważne BMM.

— virgi

No i oczywiście, możemy po prostu oprzeć twardość problemu przechodniości tylko na założonej twardości detekcji trójkąta. Zauważ, że nie ma znanych dolnych granic lepszych niż

n^{2}

$n^2$ do wykrywania trójkątów, a najlepsza górna granica to

O (n^{ω})

$O(n^\omega)$ .

— virgi

Mamy już podklubiczny praktyczny algorytm, wykorzystujący dowolną metodę szybkiego mnożenia macierzy: patrz na przykład cacm.acm.org/magazines/2014/2/…

— András Salamon

2

W cytowanym przez Ballarda i wsp. Cytowanym artykule mowa jest w szczególności o algorytmie Strassena. Z tego co wiem, żaden z algorytmów mnożenia macierzy, które używają granicy rangi, nie jest praktyczny. W szczególności nie znam praktycznych algorytmów dla jakichkolwiek ograniczeń

ω

$\omega$ niższe niż

2.78

$2.78$ .

— virgi

7

Tak to wygląda $\Omega(n^2)$ jest najlepiej znaną dolną granicą, ponieważ dowolna dolna granica oznacza dolną granicę dla mnożenia macierzy boolowskiej. Wiemy, że kontrolę przechodniości można uzyskać za pomocą jednego mnożenia macierzy boolowskiej, to znaczy $G$ jest przechodnie, jeśli i tylko jeśli $G = G^2$ .

— ekayaaslan
źródło

4

Ustalenie, czy DAG jest przechodnie, jest tak trudne, jak podjęcie decyzji, czy ogólny digraf jest przechodni (co przywraca nas do poprzedniego pytania :)).

Załóżmy, że masz algorytm działający w czasie $O(f(n))$ do decydowania, czy DAG jest przechodnie.

Biorąc pod uwagę ukierunkowany wykres $G$ , możesz użyć następującego losowego algorytmu, aby zdecydować, czy $G$ jest przechodni w czasie $O(f(n)\cdot \log(\frac{1}{\delta}))$ i prawdopodobieństwo błędu $\leq \delta$ :

 1. for $O(\log{\frac{1}{\delta}})$ iterations:

   1.1. Compute a random permutation on $V$. Denote the result by $<v_1,v_2,...,v_n>$.

   1.2. Set $G'=(V,E\cup \{(v_i,v_j)|i<j\})$ (i.e. compute a random acyclic orientation).

   1.3. If $G'$ (which is acyclic) is not transitive return false.

 2. return true.

Teraz jest oczywiste, że jeśli $G$ był przechodni, ten algorytm zwraca true.

Załóżmy teraz $G$ nie był przechodni. Pozwolić $e_1=(v_i,v_j),e_2=(v_j,v_k)\in E$ takie, że $(v_i,v_k)\notin E$ (muszą być takie krawędzie jak $G$ nie jest przechodni). Prawdopodobieństwo, że $e_1,e_2\in G'$ jest $\frac{1}{6}$ , dlatego w każdej iteracji prawdopodobieństwo obliczenia algorytmu $G$ nie był przechodni $\frac{1}{6}$ i po $O(\log{(\delta)})$ iteracje prawdopodobieństwo awarii jest co najwyżej $\delta$ .

— RB
źródło

1

Dziękuję za odpowiedź. Załóżmy, że mam algorytm do decydowania, czy DAG jest przechodni

O (f (n))

$O(f(n))$ taki

f (n) = Ω (n^{2})

$f(n)=\Omega(n^2)$ . Następnie mogę zdecydować, czy skierowany wykres G jest przechodni

O (f (n))

$O(f(n))$ -czas jak; 1) Uzyskaj silnie połączony digraf w

O (n^{2})

$O(n^2)$ -czas. 2) Sprawdź, czy każdy element jest kompletny

O (n^{2})

$O(n^2)$ -czas. 3) Sprawdź, czy każda para komponentów, dla których istnieje krawędź w digrafie komponentów, jest podwójna, tzn. Czy jest krawędź od każdego wierzchołka jednego komponentu do każdego wierzchołka drugiego komponentu w

O (n^{2})

$O(n^2)$ -czas. 4) Sprawdź, czy przechodnie digrafu komponentu jest w

O (f (n))

$O(f(n))$ -czas.

— ekayaaslan

1

Myślę, że powinno to być wykonalne w czasie liniowym, tj $O(n+m)$ gdzie $n$ to liczba wierzchołków i $m$ liczba krawędzi. Może dostosowując schemat przejścia wykresu do ukierunkowanego ustawienia? Punktem wyjścia może być opisany tutaj LexBFS / LexDFS ; w przypadku grafów ukierunkowanych wydaje się, że powinniśmy używać sortowania topologicznego zamiast DFS, więc może jest to możliwe przy użyciu jakiegoś algorytmu LexTSA ?

— Super9
źródło

2

Jest to mało prawdopodobne IMO, ponieważ dałoby probabilistyczny algorytm liniowego czasu do sprawdzania przechodniości w ogólnych digrafach, patrz moja odpowiedź.

— RB

0

Jeśli chodzi o poprzednią odpowiedź, oto prosty sposób zdefiniowania takiego algorytmu. Przypisz do każdego wierzchołka $x$ indeks $i(x)$ , zainicjowano na $0$ . Dla każdego $x$ , pozwolić $M(x)$ oznaczają zbiór wskaźników jego sąsiadów. Symulujemy sortowanie topologiczne, utrzymując zestaw $R$ niezbadanych wierzchołków, zainicjowanych do całego zestawu. Na każdym kroku wykonujemy następujące czynności:

Wybierz wierzchołek $x \in R$ którego multiset $M(x)$ jest minimalny (w kolejności wielosetowej);
Aktualizacja $i(x)$ do bieżącego licznika pętli i usuń $x$ od $R$ .

Czy można zastosować ten algorytm do rozwiązania problemu lub do innej aplikacji?

— NisaiVloot
źródło

Byłoby to bardziej odpowiednie jako komentarz.

— Suresh Venkat