Flow Problem in Tripartite Graph

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

• Edges from A are directed in B.

• 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 ?

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.

StackExchange Computer Science Q#76672, answer score: 7