# Recovering adjacency matrix from reachability matrix for DAG

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.

• In general, it doesn’t seem like it’s possible to recover the original graph. See this question, for instance.
– amd
Commented Jul 21, 2017 at 22:42
• Indeed, there will in general be multiple graphs that give rise to the same reachability matrix, even if we know that the original is a simple DAG. You'll have to be more specific. Commented Jul 22, 2017 at 14:02
• (Is this homework?) Commented Jul 22, 2017 at 14:04
• For the general case, it is not possible to recover the original graph, however for the case of DAG, I think it should be possible to recover the unique adjacency matrix with the extra constraint that the number of edges is minimal. I am more interested in 1) the constraints on the graph that a unique adjacency matrix can be recovered, and 2) the algorithm to recover it
– Amir
Commented Jul 22, 2017 at 14:30
• @JossevanDobbendeBruyn I can assure you, this is not homework! I am too old to do homeworks ;)
– Amir
Commented Jul 22, 2017 at 14:36

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

• For the infinite case, see this question. Commented Sep 28, 2017 at 3:19