Let G = (V,E,S,I,T) be a directed flow network with nodes V, edges E with unit capacity, source nodes S $\subseteq$ V, intermediate nodes I $\subseteq$ V, and target nodes T $\subseteq$ V. The problem is to find cuts C$\subseteq$ E such that the flow from S to T that visits I is maximized, and the flow from S to T that does not visit I is 0. That is, we need to place cuts to ensure that all paths from S to T are routed through I, and the flow going through I is maximized.

In particular, let $f_{SI}$ and $f_{IT}$ be the max flow on G with source-sink pairs (S,I) and (I,T), respectively. Let $F = \min\{f_{SI}, f_{IT}\}$ be the total flow through the intermediate that we wish to maximize. Let $f_{ST}$ be the max flow from S to T on the subgraph of G without the intermediate nodes: $G' = (V\setminus I, E\setminus E(I), S, T)$ (where $E(I)$ are the edges into and out of I). We will call $f_{ST}$ the bypass flow. Note that none of the flows compete for capacity. Then, the problem is to find cuts $C \subseteq E$ such that $f_{ST}=0$ and $F$ is maximized.

The question I have is on the complexity of this problem, and whether if anyone is familiar with similar problems for which the complexity class is known?



Your Answer

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