We are given two sets of terminals $A$ and $B$. For each $a\in A$, we are also given $R_a\subseteq B$. Let $|A|+|B|=n$.

We want to find a directed acyclic graph $G$ where $A$ and $B$ are subsets of the vertices, such that $a\in A$ can reach $b\in B$ if and only if $b\in R_a$. We want to optimize the number of edges.

I'm pretty sure this is studied somewhere, but I can't find the right keyword to search for it.

  • 2
    $\begingroup$ A problem that is closely related is that finding the minimum equivalent graph. Given a directed graph, find a subgraph on the same vertex set, with the exact same reachability relations (between all pairs of vertices), and having the fewest possible edges. $\endgroup$ – Neal Young May 6 '20 at 17:52
  • $\begingroup$ The if and only if condition probably makes the problem very hard to approximate. Although not directly related I would suggest looking at the hardness of approximation of the directed Steiner network problem in the paper of Dodis and Khanna. dl.acm.org/doi/10.1145/301250.301447 $\endgroup$ – Chandra Chekuri May 7 '20 at 20:52

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.