Return to Question

Input to the algorithm is a graph:

• bipartite
• directed
• all edges are directed from part one to the part two
• it's not a multigraph

The output should be a graph that satisfies the conditions:

• the graph has all vertices from the input graph
• the graph has no edges that are directed to the vertices of the part one of the initial graph
• the graph has no edges that are directed from the vertices of the part two of the initial graph
• if there is an edge between two vertices in the input graph, then there must be only one dpath between them in the graph
• if there is no edge between two vertices in the input graph, then there must be no dpath between them in the graph
• note: graph can be bipartite or not
• note: graph can have more vertices

More specifically, the output of the algorithm should be the minimal-edge-count graph among the graphs that satisfy the above conditions.

Question: is there an efficient algorithm for this task?

There is probably a loophole in my constraints. Here is a picture of these 'reachability-equivalent' graphs:

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.

Input to the algorithm is a graph:

• bipartite
• directed
• all edges are directed from part one to the part two
• it's not a multigraph

We look at a all graphs that satisfy the conditions:

• the graph has all vertices from the input graph
• the graph has no edges that are directed to the vertices of the part one of the initial graph
• the graph has no edges that are directed from the vertices of the part two of the initial graph
• if there is an edge between two vertices in the input graph, then there must be only one dpath between them in the graph
• if there is no edge between two vertices in the input graph, then there must be no dpath between them in the graph
• note: graph can be bipartite or not
• note: graph can have more vertices

Output of the algorithm: a minimal-edge-count graph among the graphs that satisfy the above conditions.

Question: what is the good algorithm?

There is probably a loophole in my constraints. Here is a picture of these 'reachability-equivalent' graphs:

Input to the algorithm is a graph:

• bipartite
• directed
• all edges are directed from part one to the part two
• it's not a multigraph

The output should be a graph that satisfies the conditions:

• the graph has all vertices from the input graph
• the graph has no edges that are directed to the vertices of the part one of the initial graph
• the graph has no edges that are directed from the vertices of the part two of the initial graph
• if there is an edge between two vertices in the input graph, then there must be only one dpath between them in the graph
• if there is no edge between two vertices in the input graph, then there must be no dpath between them in the graph
• note: graph can be bipartite or not
• note: graph can have more vertices

More specifically, the output of the algorithm should be the minimal-edge-count graph among the graphs that satisfy the above conditions.

Question: is there an efficient algorithm for this task?

There is probably a loophole in my constraints. Here is a picture of these 'reachability-equivalent' graphs:

Input to the algorithm is a graph:

• bipartite
• directed
• all edges are directed from part one to the part two
• it's not a multigraph

We look at a all graphs that satisfy the conditions:

• the graph has all vertices from the input graph
• the graph has no edges that are directed to the vertices of the part one of the initial graph
• the graph has no edges that are directed from the vertices of the part two of the initial graph
• if there is an edge between two vertices in the input graph, then there must be only one dpath between them in the graph
• if there is no edge between two vertices in the input graph, then there must be no dpath between them in the graph
• note: graph can be bipartite or not
• note: graph can have more vertices

Output of the algorithm: a minimal-edge-count graph among the graphs that satisfy the above conditions.

Question: what is the good algorithm?

Input to the algorithm is a graph:

• bipartite
• directed
• all edges are directed from part one to the part two
• it's not a multigraph

We look at a all graphs that satisfy the conditions:

• the graph has all vertices from the input graph
• the graph has no edges that are directed to the vertices of the part one of the initial graph
• the graph has no edges that are directed from the vertices of the part two of the initial graph
• if there is an edge between two vertices in the input graph, then there must be only one dpath between them in the graph
• if there is no edge between two vertices in the input graph, then there must be no dpath between them in the graph
• note: graph can be bipartite or not
• note: graph can have more vertices

Output of the algorithm: a minimal-edge-count graph among the graphs that satisfy the above conditions.

Question: what is the good algorithm?

There is probably a loophole in my constraints. Here is a picture of these 'reachability-equivalent' graphs: