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 ?

Improve this question
$\endgroup$
4
  • $\begingroup$ In fact due to the structure of Graph, the undirected solution would work for directed version too. $\endgroup$
    – J.Doe
    Jun 12, 2017 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, 2017 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, 2017 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, 2017 at 6:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2017 at 8:40
  • $\begingroup$ Possibly. You can try to prove it, just to be sure. $\endgroup$
    – Yuval Filmus
    Jun 12, 2017 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, 2017 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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