# Policy-Compliant Maximum Network Flows
## 4 Policy-Compliant Paths and Algorithms
### Third Lower Bound  
Considering the approaches taken to calculate the first and the second lower bound, observe that at several times choices have to be made, e.g., when fulfilling condition (17). Apart from the fact that some of the conditions might be overly restrictive, we face the fact that we might miss augmenting paths during the search when we make a bad choice, as well as the fact that we might need additional iterations to reach the point where no more augmenting paths can be found. For example, consider (17) and suppose that multiple states exist that fulfill the condition. By choosing one of them, an already present policy-compliant path is chosen too, which implies that the amount of flow that can be canceled has an upper bound that is equal to the minimum value of residual capacity across the backward section. In turn, this restricts the total amount of flow that can be sent over the augmenting path due to (19).  
Thus, in order to allow as much flow as possible to be sent over the augmenting path that is constructed, one can check at the same time whether other transitions can be applied in parallel, such that the total amount of flow that is canceled across the backward section is maximized. First, we want to allow multiple pre-existing policy-compliant paths that cross the cut-vertex to be involved in the process, such that we do not have to choose at all which path we want to work with in (20). Multiple policy-compliant paths might fulfill the condition, even reaching the same state in the cut-vertex but following another way to the sink. Also, we want to allow multiple states at the end of the backward section to be involved in the process, such that we do not have to choose at all which state we want to work with in (21). Multiple states might fulfill the condition, and they even might be equal to each other even though they are part of different policy-compliant paths. We need to match the possibilities in both sets to maximize the flow that we can cancel along the backward section in the middle of the augmenting path. This being, of course, under the additional condition (18).  
We start again with augmenting path \(p\), set \(P\) and set \(S\). Now select a subset \(P^{\prime}\subseteq P\) such that  
\[\forall p_{i}\in P^{\prime}:\delta^{*}(q_{u_{j}},l(e_{i}^{\prime})\ldots l(e_{ n}^{i}))\in F \tag{22}\]  
\[\forall p_{i}\in P^{\prime}:\delta^{*}(q_{u_{2}}^{i},l((v_{k},u_{k}))\ldots l ((v_{j},u_{j})))=q_{u_{j}}^{i} \tag{23}\]  
\[\forall p_{i}\in P^{\prime}:\delta^{*}(q_{v_{k}}^{i},l(e_{i})\ldots l(e_{n}))\in F \tag{24}\]  
\[\Sigma_{p_{i}\in P^{\prime}}c_{i}\leq min(c_{u_{j}},c_{v_{k}}). \tag{25}\]  
This set \(P^{\prime}\) can be iteratively built, starting from the empty set and choosing and adding \(p_{i}\)'s while (25) holds. Once the iteration comes to a stop, augment the flow along the path \(p\) with the value \(\Sigma_{p_{i}\in P^{\prime}}c_{i}\) and update \(f\) and \(T\). As the conditions (18), (20) and (21) imply that (22)-(24) will also hold, we obtain once more a tighter bound. However, there is no guarantee that the policy-compliant maximum flow will be reached. This is the most generic specification of a solution to the policy-compliant maximum flow problem that we derived.