Flow Problem in Tripartite Graph

Question

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 ?

• J.Doe: In fact due to the structure of Graph, the undirected solution would work for directed version too.
• J.Doe: 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.
• J.Doe: 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.
• J.Doe: 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).

Answer 1

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.

• J.Doe: 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 ?
• Yuval Filmus: Possibly. You can try to prove it, just to be sure.
• theyaoster: 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.