11
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Michael Lampis
    Aug 27, 2015 at 19:51
  • $\begingroup$ 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. $\endgroup$
    – Martin Vatshelle
    Aug 27, 2015 at 20:07
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Aug 28, 2015 at 6:43
  • $\begingroup$ 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. $\endgroup$
    – Martin Vatshelle
    Aug 28, 2015 at 8:04
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Aug 28, 2015 at 9:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.