1
$\begingroup$

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?

$\endgroup$

0

Your Answer

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