Kontrola przechodniości a zamknięcie przechodnie

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)$

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$.

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$.

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$.

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 ?

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:

1. Wybierz wierzchołek $x \in R$ którego multiset $M(x)$ jest minimalny (w kolejności wielosetowej);

2. 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?