<p>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&gt;0$, then you have an O($n^{3-\varepsilon}$) time algorithm for detecting a triangle in an $n$ node graph, and hence (by a <a href="http://dx.doi.org/10.1109/FOCS.2010.67" rel="noreferrer">paper from FOCS'10</a>) 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 <a href="http://dx.doi.org/10.1109/SWAT.1971.4" rel="noreferrer">Fischer and Meyer from the 70s</a>, this also implies an O($n^{3-\varepsilon/3}$) time algorithm for transitive closure. </p>

<p>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)$. </p>

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

CC BY-SA 3.0
2014-03-13T15:31:57.233Z
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.
András Salamon
CC BY-SA 3.0
2014-03-14T04:57:13.807Z
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.
virgi
CC BY-SA 3.0
2014-03-14T05:08:01.600Z
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)$.
virgi
CC BY-SA 3.0
2014-03-14T16:30:27.487Z
We already have a subcubic practical algorithm, by using any fast matrix multiplication method: see for instance http://cacm.acm.org/magazines/2014/2/171673-communication-costs-of-strassens-matrix-multiplication/abstract
András Salamon
CC BY-SA 3.0
2014-03-15T06:13:53.260Z
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$.
virgi
CC BY-SA 3.0
2014-03-13T00:12:47.593Z
2014-03-13T18:00:59.390Z
2014-03-13T18:00:59.390Z
virgi
<p>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$.</p>

CC BY-SA 3.0
2014-03-12T15:21:59.473Z
2014-03-17T15:52:56.027Z
2014-03-17T15:52:56.027Z
ekayaaslan
<p>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 :) ).</p>

<p>Assume you have an algorithm running in time $O(f(n))$ for deciding if a DAG is transitive.</p>

<p>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$:</p>

<pre><code> 1. for $O(\log{\frac{1}{\delta}})$ iterations:

   1.1. Compute a random permutation on $V$. Denote the result by $&lt;v_1,v_2,...,v_n&gt;$.

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

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

 2. return true.
</code></pre>

<p>Now it is obvious that if $G$ was transitive, this algorithm return true.</p>

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

CC BY-SA 3.0
2014-03-11T21:43:17.960Z
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.
ekayaaslan
CC BY-SA 3.0
2014-03-11T21:03:55.223Z
2014-03-11T21:37:17.130Z
2014-03-11T21:37:17.130Z
R B
<p>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 <em>LexBFS</em> / <em>LexDFS</em> described <a href="http://citeseerx.ist.psu.edu/showciting?cid=4369072" rel="nofollow">here</a>; for directed graphs it seems that we should use topological sorting rather than DFS, so maybe it's possible with some <em>LexTSA</em> algorithm to discover?</p>

CC BY-SA 3.0
2014-03-11T22:44:07.493Z
This is unlikely IMO, as it would give a probabilistic linear time algorithm for transitivity checking in general digraphs, see my answer.
R B
CC BY-SA 3.0
2014-03-11T22:30:42.263Z
2014-03-11T22:30:42.263Z
Super9
<p>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:</p>

<ol>
<li><p>Chose a vertex $x \in R$ whose multiset $M(x)$ is minimal (in the multiset order);</p></li>
<li><p>Update $i(x)$ to the current loop counter and remove $x$ from $R$.</p></li>
</ol>

<p>Can this algorithm be used for your problem, or for some other application?</p>

CC BY-SA 3.0
2014-03-24T07:30:40.333Z
This would be more appropriate as a comment.
Suresh Venkat
CC BY-SA 3.0
2014-03-18T11:34:54.020Z
2014-03-18T11:34:54.020Z
NisaiVloot
<p>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?</p>

CC BY-SA 3.0
2014-03-10T18:18:40.950Z
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
Chad Brewbaker
CC BY-SA 3.0
2014-03-10T18:26:25.680Z
Here, Siek has implementation notes for the Boost Graph Library http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/transitive_closure.html
Chad Brewbaker
CC BY-SA 3.0
2014-03-10T18:35:21.710Z
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.
R B
CC BY-SA 3.0
2014-03-10T21:44:30.877Z
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.
András Salamon
CC BY-SA 3.0
2014-03-11T20:41:35.977Z
Does your DAG possibly have any additional structure, or do you want fully general results?
Niel de Beaudrap
CC BY-SA 3.0
2014-03-11T22:52:37.273Z
For this question, we assume $|E|=\Theta(|V|^2)$. However the sparse case, $|E|=\Theta(|V|)$, is also interesting.
ekayaaslan
<graph-theory><directed-acyclic-graph><transitive-closure>
Transitivity check vs. Transitive Closure
ekayaaslan
# Transitivity check vs. Transitive Closure

(Asked by: username_0 on 2014-03-10)

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?

**Tags:** graph-theory, directed-acyclic-graph, transitive-closure
> **Comments:**
> **username_1**: 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  
> **username_1**: Here, Siek has implementation notes for the Boost Graph Library http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/transitive_closure.html  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: Does your DAG possibly have any additional structure, or do you want fully general results?  
> **username_0**: For this question, we assume $|E|=\Theta(|V|^2)$. However the sparse case, $|E|=\Theta(|V|)$, is also interesting.  

---

## 5 answers

### Answer by username_5 on 2014-03-13. Score: 10

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](http://dx.doi.org/10.1109/FOCS.2010.67)) 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](http://dx.doi.org/10.1109/SWAT.1971.4), 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$.

> **Comments:**
> **username_3**: 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.  
> **username_5**: 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.  
> **username_5**: 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)$.  
> **username_3**: We already have a subcubic practical algorithm, by using any fast matrix multiplication method: see for instance http://cacm.acm.org/magazines/2014/2/171673-communication-costs-of-strassens-matrix-multiplication/abstract  
> **username_5**: 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$.  

---

### Answer by username_0 on 2014-03-12. Score: 7

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


---

### Answer by username_2 on 2014-03-11. Score: 4

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

   1.2. Set $G'=(V,E\cup \{(v_i,v_j)|i
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$.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_6 on 2014-03-11. Score: 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](http://citeseerx.ist.psu.edu/showciting?cid=4369072); 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?

> **Comments:**
> **username_2**: This is unlikely IMO, as it would give a probabilistic linear time algorithm for transitivity checking in general digraphs, see my answer.  

---

### Answer by username_7 on 2014-03-18. Score: 0

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:

1. Chose a vertex $x \in R$ whose multiset $M(x)$ is minimal (in the multiset order);
2. 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?

> **Comments:**
> **username_8**: This would be more appropriate as a comment.  

---

