# Network design with reachability pattern

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.

• 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. – Neal Young May 6 at 17:52
• 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 – Chandra Chekuri May 7 at 20:52