<p>We are given two sets of terminals <span class="math-container">$A$</span> and <span class="math-container">$B$</span>. For each <span class="math-container">$a\in A$</span>, we are also given <span class="math-container">$R_a\subseteq B$</span>. Let <span class="math-container">$|A|+|B|=n$</span>.</p>

<p>We want to find a directed acyclic graph <span class="math-container">$G$</span> where <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are subsets of the vertices, such that <span class="math-container">$a\in A$</span> can reach <span class="math-container">$b\in B$</span> if and only if <span class="math-container">$b\in R_a$</span>. We want to optimize the number of edges.</p>

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

CC BY-SA 4.0
2020-05-06T17:52:31.240Z
A problem that is closely related is that finding [the minimum equivalent graph](https://en.wikipedia.org/wiki/Transitive_reduction).  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
CC BY-SA 4.0
2020-05-07T20:52:11.880Z
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. https://dl.acm.org/doi/10.1145/301250.301447
Chandra Chekuri
<reference-request><graph-theory>
Network design with reachability pattern
Chao Xu
# Network design with reachability pattern

(Asked by: username_0 on 2020-05-06)

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.

**Tags:** reference-request, graph-theory

> **Comments:**
> **username_1**: A problem that is closely related is that finding [the minimum equivalent graph](https://en.wikipedia.org/wiki/Transitive_reduction).  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.  
> **username_2**: 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. https://dl.acm.org/doi/10.1145/301250.301447  

---

## 0 answers

