<p>Let's assume that $D$ contains only sources and sinks, since the input can be translated into an equivalent such input easily.</p>

<p>Then, note that, in any solution $D'$ for $D$, each vertex $v$ corresponds to a biclique in the underlying undirected graph $G$ of $D$ (the biclique between all sources that reach $v$ in $D'$ and all sinks that are reached from $v$ in $D'$).</p>

<p>I conjecture that, if $D'$ is optimal, then it contains a vertex-cut that 1:1 corresponds to an optimal biclique covering of $G$. Then, any minimum vertex-cut in $D'$ corresponds to an optimal biclique covering in $G$. However, since BICLIQUE COVER (aka BIPARTITE DIMENSION) is NP-complete, your problem is unlikely to admit a polynomial-time algorithm unless my conjecture fails.</p>

<p>Note that, even if my conjecture holds, technically this argument does not prove NP-hardness of your problem, since the reduction is not a Karp- but a Cook reduction.</p>

CC BY-SA 3.0
2015-10-23T08:06:28.303Z
2015-10-23T10:17:22.390Z
2015-10-23T10:17:22.390Z
igel
<p>Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$.
Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that:</p>

<p>For all pairs $u \in S, v \in T$ there is a path from $u$ to $v$ in $D$ if and only if there is a path from $u$ to $v$ in $D'$.</p>

<p>One application of this is representing a set family by a DAG.
For such a representation each source is a variable in the universe and each sink is a set in the set family, and a element u is in a set S if and only if there is a path from the vertex representing u to the vertex representing the set S.</p>

<p>Is this problem well known?
Is there a polynomial algorithm for this problem?</p>

CC BY-SA 3.0
2015-08-27T19:51:46.870Z
I guess the solution must be a subgraph of the original graph, right? If yes, I think this problem captures Set Cover, through the standard reduction that shows the Directed Steiner Tree is hard: Create a vertex for each element, a vertex for each set, and a directed edge (S,u) if the set S contains element u. Then add a new vertex and edges from it to all set vertices. There is a path from this new vertex to all sinks (the element vertices). In order to preserve all of them we have to select the minimum number of set vertices that covers all elements.
Michael Lampis
CC BY-SA 3.0
2015-08-27T20:07:09.113Z
No, in general I would say it should not be a subgraph of the original graph. Sources are elements and you need on element if and only if some set contains that element. Sinks are sets and you can not delete the sets you are supposed to represent so the only thing one can do if one starts from the naive graph where all nodes are either sinks or sources is to add vertices and move/delete edges.
Martin Vatshelle
CC BY-SA 3.0
2015-08-28T06:43:38.657Z
The problem doesn't seem well-defined yet.  What are the restrictions on the vertex set of $D'$?  Do you require that the vertex set of $D'$ is the same as the vertex set of $D$?  That the sources and sinks of $D'$ are the same as the sources and sinks of $D$?  That there is a function $f:V_D \to V_{D'}$ mapping a vertex of $D$ to a vertex of $D'$, and the condition is actually that there's a path from $u$ to $v$ in $D$ iff there's a path from $f(u)$ to $f(v)$ in $D'$?  Each one might lead to a  slightly different problem.  Edit the question to clarify?
D.W.
CC BY-SA 3.0
2015-08-28T08:04:40.633Z
I clarified the question, indeed I mean that the sources and sinks are the same.
I think the mapping is quite close to the same, the only way one could map two sinks to the same node is if they are reachable from the same set of sources, i.e. represents the same set. The only way two sources could be mapped to same node is if they reach exactly the same sinks. So I think after some simple preprocessing of D the problems would be equivalent.
Martin Vatshelle
CC BY-SA 3.0
2015-08-28T09:11:18.560Z
The dag D is actually irrelevant to the problem, isn't it? You could as well take a bipartite graph between S and T as input.
Emil Jeřábek
CC BY-SA 3.0
2015-08-28T09:29:35.357Z
Yes, any DAG which has the same source sink reachability are considered equivalent, so one could reduce it to the one with only sources and sinks first and use that as input.
Martin Vatshelle
CC BY-SA 3.0
2015-09-08T17:27:54.743Z
@PalGD So what? I was just pointing out that most of the input data are redundant. I made no claims about the size.
Emil Jeřábek
CC BY-SA 3.0
2015-09-09T19:46:23.960Z
Just to be sure I understand, you are allowed to have a path $s_1 \to t_1 \to s_2 \to t_2$ where $s_i$ are sources and $t_i$ are sinks, and $s_1$ reaches $t_1$ and $t_2$?
John K.
CC BY-SA 3.0
2015-09-10T10:52:36.993Z
No, sources should only have outgoing arcs and sinks should only have incoming arcs.
Martin Vatshelle
CC BY-SA 3.0
2015-09-24T08:25:14.523Z
What is wrong with starting with S and T, and for each s in S and t in T checking whether there is an st-path in logspace; there is an edge from s to t in $D'$ off there is an st-path in $D$?
András Salamon
CC BY-SA 4.0
2024-03-02T13:56:33.027Z
Speaking vaguely, this problem seems somewhat similar in spirit to the notorious MCSP (the [Minimum Circuit Size Problem](https://scholar.google.com/scholar?hl=en&as_sdt=0,22&q=%22Minimum+Circuit+Size+Problem%22&scisbd=1)).   Some variants of MCSP are known to be NP-hard.  Perhaps you could look for ideas for an NP-hardness proof for your problem in the proofs of those NP-hardness results.
Neal Young
CC BY-SA 4.0
2024-03-12T08:45:20.537Z
@NealYoung Thank you, that is a nice observation I will look into. I agree it is very similar. If I want to make a circuit that says for any true-false assignment of sources, a sink is set to true iff it is reachable from one of the sources assigned true. But it seems I only need OR gates to solve this, so that would make it an easier problem than MCSP. But since we have many sinks we dont have only one boolean function and we can not minimize each sink independently so that indicates it is harder.
Martin Vatshelle
CC BY-SA 4.0
2024-03-12T16:30:01.487Z
See https://doi.ieeecomputersociety.org/10.1109/FOCS57990.2023.00048 for recent progress on MCSP.
Neal Young
<graph-theory><graph-algorithms>
Minimum equivalent digraph with respect to sources and sinks
Martin Vatshelle
# Minimum equivalent digraph with respect to sources and sinks

(Asked by: username_0 on 2015-08-27)

Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$.
Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that:

For all pairs $u \in S, v \in T$ there is a path from $u$ to $v$ in $D$ if and only if there is a path from $u$ to $v$ in $D'$.

One application of this is representing a set family by a DAG.
For such a representation each source is a variable in the universe and each sink is a set in the set family, and a element u is in a set S if and only if there is a path from the vertex representing u to the vertex representing the set S.

Is this problem well known?
Is there a polynomial algorithm for this problem?

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: I guess the solution must be a subgraph of the original graph, right? If yes, I think this problem captures Set Cover, through the standard reduction that shows the Directed Steiner Tree is hard: Create a vertex for each element, a vertex for each set, and a directed edge (S,u) if the set S contains element u. Then add a new vertex and edges from it to all set vertices. There is a path from this new vertex to all sinks (the element vertices). In order to preserve all of them we have to select the minimum number of set vertices that covers all elements.  
> **username_0**: No, in general I would say it should not be a subgraph of the original graph. Sources are elements and you need on element if and only if some set contains that element. Sinks are sets and you can not delete the sets you are supposed to represent so the only thing one can do if one starts from the naive graph where all nodes are either sinks or sources is to add vertices and move/delete edges.  
> **username_2**: The problem doesn't seem well-defined yet.  What are the restrictions on the vertex set of $D'$?  Do you require that the vertex set of $D'$ is the same as the vertex set of $D$?  That the sources and sinks of $D'$ are the same as the sources and sinks of $D$?  That there is a function $f:V_D \to V_{D'}$ mapping a vertex of $D$ to a vertex of $D'$, and the condition is actually that there's a path from $u$ to $v$ in $D$ iff there's a path from $f(u)$ to $f(v)$ in $D'$?  Each one might lead to a  slightly different problem.  Edit the question to clarify?  
> **username_0**: I clarified the question, indeed I mean that the sources and sinks are the same. I think the mapping is quite close to the same, the only way one could map two sinks to the same node is if they are reachable from the same set of sources, i.e. represents the same set. The only way two sources could be mapped to same node is if they reach exactly the same sinks. So I think after some simple preprocessing of D the problems would be equivalent.  
> **username_3**: The dag D is actually irrelevant to the problem, isn't it? You could as well take a bipartite graph between S and T as input.  
> **username_0**: Yes, any DAG which has the same source sink reachability are considered equivalent, so one could reduce it to the one with only sources and sinks first and use that as input.  
> **username_3**: @PalGD So what? I was just pointing out that most of the input data are redundant. I made no claims about the size.  
> **username_4**: Just to be sure I understand, you are allowed to have a path $s_1 \to t_1 \to s_2 \to t_2$ where $s_i$ are sources and $t_i$ are sinks, and $s_1$ reaches $t_1$ and $t_2$?  
> **username_0**: No, sources should only have outgoing arcs and sinks should only have incoming arcs.  
> **username_5**: What is wrong with starting with S and T, and for each s in S and t in T checking whether there is an st-path in logspace; there is an edge from s to t in $D'$ off there is an st-path in $D$?  
> **username_6**: Speaking vaguely, this problem seems somewhat similar in spirit to the notorious MCSP (the [Minimum Circuit Size Problem](https://scholar.google.com/scholar?hl=en&as_sdt=0,22&q=%22Minimum+Circuit+Size+Problem%22&scisbd=1)).   Some variants of MCSP are known to be NP-hard.  Perhaps you could look for ideas for an NP-hardness proof for your problem in the proofs of those NP-hardness results.  
> **username_0**: @NealYoung Thank you, that is a nice observation I will look into. I agree it is very similar. If I want to make a circuit that says for any true-false assignment of sources, a sink is set to true iff it is reachable from one of the sources assigned true. But it seems I only need OR gates to solve this, so that would make it an easier problem than MCSP. But since we have many sinks we dont have only one boolean function and we can not minimize each sink independently so that indicates it is harder.  
> **username_6**: See https://doi.ieeecomputersociety.org/10.1109/FOCS57990.2023.00048 for recent progress on MCSP.  

---

## 1 answers

### Answer by username_7 on 2015-10-23. Score: 1

Let's assume that $D$ contains only sources and sinks, since the input can be translated into an equivalent such input easily.

Then, note that, in any solution $D'$ for $D$, each vertex $v$ corresponds to a biclique in the underlying undirected graph $G$ of $D$ (the biclique between all sources that reach $v$ in $D'$ and all sinks that are reached from $v$ in $D'$).

I conjecture that, if $D'$ is optimal, then it contains a vertex-cut that 1:1 corresponds to an optimal biclique covering of $G$. Then, any minimum vertex-cut in $D'$ corresponds to an optimal biclique covering in $G$. However, since BICLIQUE COVER (aka BIPARTITE DIMENSION) is NP-complete, your problem is unlikely to admit a polynomial-time algorithm unless my conjecture fails.

Note that, even if my conjecture holds, technically this argument does not prove NP-hardness of your problem, since the reduction is not a Karp- but a Cook reduction.


---

