Recovering adjacency matrix from reachability matrix for DAG

Question

The problem of computing the reachability from adjacency matrix of a graph is well-known, but is there an algorithm for recovering the adjacency matrix from the reachability matrix for directed acyclic graph.

Answer 1

The graph you're looking for is the transitive reduction of the reachability DAG (see also: Hasse diagram). It not only has minimal number of edges, but it must in fact be contained in any graph with the same reachability matrix.

Suppose that we are given a reachability matrix. Note that this is the adjacency matrix of a transitively closed DAG $G = (V,A)$. We may furthermore interpret this as a partial order on the vertex set: we write $v < w$ if and only if $(v,w) \in A$, that is, $w$ is reachable from $v$. It is readily verified that this is indeed a strict partial order. Now we define the transitive reduction $G' = (V,A)$ by choosing the following arc set: $$ A' = \{(v,w) \in A \, : \, \text{there does not exist a vertex $x$ such that}\ v < x < w\}. $$ (We say that $w$ covers $v$ if no such vertex $x$ exists.) Clearly every element of $A'$ must necessarily be included in our DAG: if we remove a covering arc $(v,w)$ then no paths from $v$ to $w$ remain.

On the other hand, it is not very hard to show that $G'$ defines the same reachability relation. Suppose that we have $v < w$. Now extend this to a maximal chain $v = x_1 < x_2 < \cdots < x_k = w$, then every step must be covering (otherwise the chain would not be maximal). This defines a path from $v$ to $w$ in $G'$, so we see that $w$ is indeed reachable from $v$.

Thus, we have found a unique minimal arc set $A'$ that defines the given reachability relation. How do we compute it? There is a trivial $O(|V|\cdot |A|)$ algorithm: for each arc $(v,w)\in A$ check all vertices $x\in V$ to see whether or not the pair $(v,w)$ is covering. Both Wikipedia and Computer Science Stack Exchange seem to suggest that we cannot do much better (although I think they consider the problem where the given graph is not yet transitively closed).

Furthermore, the above discussion gives us a uniqueness criterion. A directed graph $\tilde G = (V,\tilde A)$ has reachability graph $G$ if and only if $A' \subseteq \tilde A \subseteq A$ holds. Therefore the following are equivalent:

• There is a unique DAG with reachability graph $G$.
• The equality $A' = A$ holds (that is, $G$ is equal to its reduction $G'$).
• Every pair $v < w$ is covering.
• There are no chains with three or more elements.
• $G$ has no paths of length $2$ or more.

(If we know a priori that the solution is unique, then there is an $O(1)$ algorithm: the adjacency matrix is equal to the given reachability matrix.)