Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to determine if a digraph is transitive or not?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ Storing the entire transitive closure will cost you extra space. For some graphs you should be able to hook and shortcut the transitivity check without revisiting edges. See: An $O(log n)$ parallel connectivity algorithm, Y Shiloach, U Vishkin - Journal of Algorithms, 1982 $\endgroup$– Chad BrewbakerCommented Mar 10, 2014 at 18:18
-
1$\begingroup$ Here, Siek has implementation notes for the Boost Graph Library boost.org/doc/libs/1_54_0/libs/graph/doc/… $\endgroup$– Chad BrewbakerCommented Mar 10, 2014 at 18:26
-
2$\begingroup$ Not sure what you mean by $n$, but a lower bound of $\Omega(|V|^2)$ is simple - consider $K_n \setminus \{e\}$ for some edge $e$. Any algorithm will ask have to check if $(u,v)\in E$ for all $u,v\in V$, as otherwise the edge he didn't ask about could be the one missing. $O(|V|\cdot |E|)$ is an upper bound, as this is the time it takes to compute a transitive closure. $\endgroup$– R BCommented Mar 10, 2014 at 18:35
-
2$\begingroup$ Consider a directed graph with $n = 3k$ vertices: source vertices $s_1,\dots,s_k$, intermediate vertices $t_1,\dots,t_k$ that are immediate successors of each $s_i$, and sink vertices $u_1,\dots,u_k$ that are immediate successors of each $t_i$. The digraph is transitive iff each of the arcs $(s_i,u_j)$ is present in the graph. This requires checking $k^2 = (n/3)^2 = \Omega(n^2)$ edges. On the other hand, finding transitive closure can be done in $O(n^\omega)$ time, where $\omega < 2.373$ is the exponent of matrix multiplication. These are the best known bounds. $\endgroup$– András SalamonCommented Mar 10, 2014 at 21:44
-
$\begingroup$ Does your DAG possibly have any additional structure, or do you want fully general results? $\endgroup$– Niel de BeaudrapCommented Mar 11, 2014 at 20:41
|
Show 1 more comment
5 Answers
$\begingroup$
$\endgroup$
5
Below I'll show the following: if you have an O($n^{3-\varepsilon}$) time algorithm for checking if a graph is transitive for any $\varepsilon>0$, then you have an O($n^{3-\varepsilon}$) time algorithm for detecting a triangle in an $n$ node graph, and hence (by a paper from FOCS'10) you'd have an O($n^{3-\varepsilon/3}$) time algorithm for multiplying two boolean $n\times n$ matrices, and hence by a result of Fischer and Meyer from the 70s, this also implies an O($n^{3-\varepsilon/3}$) time algorithm for transitive closure.
Suppose that you want to detect a triangle in an $n$ node $G$. We can now create the following graph $H$. $H$ is tripartite with partitions $I,J,K$ on $n$ nodes each. Here each node $x$ of $G$ has copies $x_I,x_J,x_K$ in the parts $I,J,K$. For each edge $(u,v)$ of $G$ add directed edges $(u_I,v_J)$ and $(u_J,v_K)$. For each nonedge $(u,v)$ of $G$ add the directed edge $(u_I,v_K)$.
First, if $G$ contains a triangle $u,v,w$, then $H$ is not transitive. This is since the edges $(u_I,v_J),(v_J,w_K)$ are in $H$ but $(u_I,w_K)$ is not. Second, if $H$ is not transitive, then there must exist some directed path from some node $s$ to some node $t$ in $H$ such that $(s,t)$ is not a directed edge in $H$. However, the longest paths in $H$ have $2$ edges, and so any such path must be of the form $(u_I,v_J),(v_J,w_K)$ and $(u_I,w_K)$ is not in $H$, hence $u,v,w$ form a triangle in $G$.
-
1$\begingroup$ Finding transitive closure is essentially the same as matrix multiplication. The question is whether the exponent in the lower bound can be raised from 2, or the exponent in the upper bound can be lowered from 2.373. The chain of reasoning you demonstrate shows that even an optimal $O(n^2)$ algorithm for checking transitivity would only yield an $O(n^{2.667})$ time algorithm for transitive closure -- but we already have an $O(n^{2.373})$ time algorithm. $\endgroup$ Commented Mar 13, 2014 at 15:31
-
$\begingroup$ The point is that black box reductions exist. The O($n^{2.373}$) time algorithm is far from practical. A practical transitivity checking algorithm that runs in subcubic time however, by the above reductions also implies a practical one for BMM and hence transitive closure. Also, even if you don't care about practical algorithms, it is quite possible that the loss in the exponent from the FOCS'10 paper is not necessary, and triangle detection is probably equivalent to BMM. $\endgroup$– virgiCommented Mar 14, 2014 at 4:57
-
$\begingroup$ Oh and of course, we could just base the hardness of the transitivity problem just on the presumed hardness of triangle detection. Note that there are no known lower bounds better than $n^2$ for triangle detection, and the best upper bound is $O(n^\omega)$. $\endgroup$– virgiCommented Mar 14, 2014 at 5:08
-
$\begingroup$ We already have a subcubic practical algorithm, by using any fast matrix multiplication method: see for instance cacm.acm.org/magazines/2014/2/… $\endgroup$ Commented Mar 14, 2014 at 16:30
-
2$\begingroup$ The Ballard et al paper that you cite talks about Strassen's algorithm in particular. From what I know, none of the matrix multiplication algorithms that use border rank are practical. In particular, I am not aware of practical algorithms for any bound on $\omega$ lower than $2.78$. $\endgroup$– virgiCommented Mar 15, 2014 at 6:13
$\begingroup$
$\endgroup$
It looks like that $\Omega(n^2)$ is the best known lower bound, since any lower bound implies a lower bound for boolean matrix multiplication. We know that transitivity check can be achieved using one boolean matrix multiplication, that is, $G$ is transitive if and only if $G = G^2$.
$\begingroup$
$\endgroup$
1
Figuring if a DAG is transitive is as hard as deciding if a general digraph is transitive (which bring us back to your previous question :) ).
Assume you have an algorithm running in time $O(f(n))$ for deciding if a DAG is transitive.
Given a directed graph $G$, you can use the following randomized algorithm to decide if $G$ is transitive in time $O(f(n)\cdot \log(\frac{1}{\delta}))$ and error probability $\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.
Now it is obvious that if $G$ was transitive, this algorithm return true.
Now assume $G$ wasn't transitive. Let $e_1=(v_i,v_j),e_2=(v_j,v_k)\in E$ such that $(v_i,v_k)\notin E$ (there has to be such edges as $G$ is not transitive). The probability that $e_1,e_2\in G'$ is $\frac{1}{6}$, therefore in each iteration the probability that the algorithm will figure $G$ wasn't transitive is $\frac{1}{6}$ and after $O(\log{(\delta)})$ iterations the failure probability is at most $\delta$.
-
1$\begingroup$ Thanks for the answer. Assume I have an algorithm for deciding if a DAG is transitive in $O(f(n))$ such $f(n)=\Omega(n^2)$. Then, I can decide if a directed graph G is transitive in $O(f(n))$-time as; 1) Obtain strongly connected digraph in $O(n^2)$-time. 2) Check if each component is complete in $O(n^2)$-time. 3) Check if each pair of components, for which there is an edge in the component digraph, is bi-complete, that is there is an edge from every vertex of one component to every vertex of the second component in $O(n^2)$-time. 4) Check if the component digraph transitive in $O(f(n))$-time. $\endgroup$ Commented Mar 11, 2014 at 21:43
$\begingroup$
$\endgroup$
1
I think this should be feasible in linear time, i.e. $O(n+m)$ where $n$ is the number of vertices and $m$ the number of edges. Maybe by adapting some graph traversal scheme to the directed setting? A starting point could be the LexBFS / LexDFS described here; for directed graphs it seems that we should use topological sorting rather than DFS, so maybe it's possible with some LexTSA algorithm to discover?
-
2$\begingroup$ This is unlikely IMO, as it would give a probabilistic linear time algorithm for transitivity checking in general digraphs, see my answer. $\endgroup$– R BCommented Mar 11, 2014 at 22:44
$\begingroup$
$\endgroup$
1
Regarding the previous answer, here's a simple way of defining such an algorithm. Assign to each vertex $x$ an index $i(x)$, initialized to $0$. For each $x$, let $M(x)$ denote the multiset of indices of its in-neighbors. We simulate a topological sorting by maintaining a set $R$ of unexplored vertices, initialized to the entire set. At each step, we do the following:
Chose a vertex $x \in R$ whose multiset $M(x)$ is minimal (in the multiset order);
Update $i(x)$ to the current loop counter and remove $x$ from $R$.
Can this algorithm be used for your problem, or for some other application?
-
$\begingroup$ This would be more appropriate as a comment. $\endgroup$ Commented Mar 24, 2014 at 7:30