I'm looking for an algorithm that, given a directed bipartite graph, builds another graph (possibly with additional vertices) that has fewer total edges but the same reachability patterns. In particular:
The input to the algorithm is a bipartite directed graph $G'=(V,E)$ with all edges directed from $L$ to $R$ (where $V=L\cup R$) and no repeated edges.
The output should be a directed graph $G'=(V',E')$ that satisfies the following conditions, and that minimizes $|E'|$:
- $G'$ has all vertices from the input graph and possibly additional ones, i.e., $V \subseteq V'$
- $G'$ no edges into $L$ and no edges into $R$
- for each edge $\ell \to r$ in $G$, there is a single path $\ell \leadsto r$ in $G'$ (one and only one path)
- for each $\ell \in L, r \in r$, if there is a path $\ell \leadsto r$ in $G'$, then there is an edge $\ell \to r$ in $G$
In particular, the output of the algorithm should be the minimal-edge-count graph among the set of all graphs that satisfy the above conditions.
Roughly speaking: given a directed bipartite graph, we want to find another directed graph that's "reachability-equivalent" in some sense and that has the fewest number of edges possible.
Question: is there an efficient algorithm for this task?
Here is a picture of these 'reachability-equivalent' graphs to show that it is possible to achieve a non-trivial reduction in the number of edges:
This is like finding a transitive reduction (or minimum equivalent graph) of a particular kind of dag, but where we're allowed to add additional vertices.
