5
$\begingroup$

Given a Directed Tripartite graph with 3 Groups of vertices {A, B, C} such that:

  1. Edges from A are directed in B.
  2. Edges from B are directed in C.

Objective: Minimize the number of vertices in B (by keeping few and deleting the rest) such that every vertex in C is reachable from every vertex in A.

I think this can be converted into a flow problem but i am not sure how to go about it. Anyone ?

$\endgroup$
  • $\begingroup$ In fact due to the structure of Graph, the undirected solution would work for directed version too. $\endgroup$ – J.Doe Jun 12 '17 at 5:18
  • 1
    $\begingroup$ Just read about it, in arborescence we have exactly 1 directed path (from vertices in A to C but we are asking for at least 1 directed path from vertices in A to C. So I think they aren't same. $\endgroup$ – J.Doe Jun 12 '17 at 5:36
  • 1
    $\begingroup$ If we are allowed to delete edges ((A->B), (B->C)) from the remaining vertices in B then I think our problem still requires to minimize the number of vertices in B (where as in spanning tree/arborescence we are concerned about minimizing the edges if I am correct. $\endgroup$ – J.Doe Jun 12 '17 at 5:41
  • $\begingroup$ Not an issue. thank you. I think a similar problem can be constructed using a bipartite graph with B remaining as it is and instead of {A, C} we have a single set {A'}. Then the condition changes to: For each pair of vertices {p, q} in A', the diameter of directed distance b/w them is exactly 2 (via B). $\endgroup$ – J.Doe Jun 12 '17 at 6:43
7
$\begingroup$

The decision version of this problem is NP-hard (and so NP-complete), by reduction from Hitting Set.

Let $S_1,\ldots,S_m$ be an instance of hitting set. We will have the following vertices and edges:

  • Vertices $A_i$ for $1 \leq i \leq m$ and $A_{i,j}$ for $1 \leq i \neq j \leq m$.
  • Vertices $B_u$ for every $u$ in the universe of the hitting set instance, and $B_{i,j}$ for $1 \leq i \neq j \leq m$.
  • Vertices $C_i$ for $1 \leq i \leq m$ and $C_{i,j}$ for $1 \leq i \neq j \leq m$.
  • For every $u \in S_i$, edges $A_i \to B_u \to C_i$.
  • For every $1 \leq i \neq j \leq m$, edges $A_{i,j} \to B_{i,j} \to C_{i,j}$.
  • For every $1 \leq i \neq j \leq m$, edges $A_i \to B_{i,j} \to C_j$.

Every feasible solution to this instance of your problem has to contain each $B_{i,j}$, since this is the only way to connect $A_{i,j}$ and $C_{i,j}$. Hence every $A_i$ is automatically connected to every $C_j$ for $j \neq i$. In order to connect $A_i$ to $C_i$, we need to have $B_u$ for some $u \in S_i$. Hence the minimal solution contains $m(m-1) + k$ vertices iff the hitting set instance has a minimal solution with $k$ elements.

$\endgroup$
  • $\begingroup$ thank you. I suppose the similar problem I mentioned in a comment above: 'a bipartite graph with B remaining as it is and instead of {A, C} we have a single set {A'}. Then the condition changes to: For each pair of vertices {p, q} in A', the diameter of directed distance b/w them is exactly 2 (via B).' This too is NP Complete then ? $\endgroup$ – J.Doe Jun 12 '17 at 8:40
  • $\begingroup$ Possibly. You can try to prove it, just to be sure. $\endgroup$ – Yuval Filmus Jun 12 '17 at 9:34
  • $\begingroup$ There is a similar reduction from Minimal Vertex Cover, where given a graph $G$ we construct $A$ to be a set of vertices $a_{uv}$, one per edge $(u,v) \in G$, $B$ is just the vertex set of $G$, and $C$ is a singleton of a vertex $z$. There are edges $(a_{uv}, u)$ and $(a_{uv}, v)$ for each $a_{uv} \in A$, and for each $b \in B$ we have the edge $(b,z)$. In this graph, a subset $B'$ of $B$ is a solution to OP's problem if and only if $B'$ is a vertex cover of $G$; it follows that the minimal solutions of both problems are equivalent. $\endgroup$ – theyaoster Jun 13 '17 at 2:31

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.