1
$\begingroup$

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:

example graphs

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.

$\endgroup$
  • 1
    $\begingroup$ Since there is a question here now: What have you tried? Where did you get stuck? $\endgroup$ – Raphael Aug 3 '16 at 12:45
  • 1
    $\begingroup$ And where are you stuck finding an algorithm? $\endgroup$ – Raphael Aug 3 '16 at 12:59
  • $\begingroup$ @Raphael, the idea is to take an empty graph and then add one by one the vertices of the second part (only with the necessary vertices from the first part). On each step look at the existing vertices of the first part ant try to find sets that are "used" by multiple vertices of the second part. Add intermediate nodes. The condition when to add is still vague. $\endgroup$ – Velkan Aug 3 '16 at 13:31
  • $\begingroup$ This usually works better if you try hard to find an algorithm on your own before asking here, and explain in the question what you've tried. For instance, if you have some ideas on candidate approaches, you should be able to implement them and run them on lots of test cases to see if they produce the optimal answer (before asking) and tell us what does/doesn't work. $\endgroup$ – D.W. Aug 3 '16 at 16:12
  • $\begingroup$ See edit. Some related ideas: Since we can add extra vertices, this reminds me a bit of the Steiner tree problem. (There does exist a Steiner graph problem, but it's something different, alas.) Also see cs.stackexchange.com/q/40472/755 and cs.stackexchange.com/a/29670/755 (also something different, alas). $\endgroup$ – D.W. Aug 3 '16 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.