# Policy-Compliant Maximum Network Flows
## 4 Policy-Compliant Paths and Algorithms
### Second Lower Bound
Indeed, as the first section \([e_{1},\ldots,e_{i}]\) is glued together with some policy-compliant path \(p_{i}\in P\) at vertex \(u_{j}\) via condition (20), we are looking for states \(q_{v_{k}}\in Q\) at vertex \(v_{k}\) such that, instead of (17) the following formula holds: \[\exists q_{v_{k}}\in Q:\delta^{*}(q_{v_{k}},l((v_{k},u_{k}))\ldots l((v_{j},u_{ j})))=q^{i}_{u_{j}}.\] (21) Indeed, after crossing section \([e_{j},\ldots,e_{k}]\) in reverse direction we want to end in state \(q^{i}_{u_{j}}\) instead of \(q_{u_{j}}\). 5. Having fulfilled the condition to allow canceling flow across the backward section of the augmenting path, we now need to check whether the flow arriving in \(v_{k}\) in state \(q_{v_{k}}\) can actually be diverted via the last forward section \([e_{l},\ldots,e_{n}]\) to the sink \(t\) reaching state \(q_{t}\) which needs to be a final state. This is accurately expressed by (18) which we can leave unmodified. 6. Suppose conditions (18), (20) and (21) have been fulfilled. Then calculate the residual capacity (19). Update flow \(f\) via (9) across the augmenting path using the value for the residual capacity, and update transitions-function \(T\) across the augmenting path as done previously. 7. Finally, we need to update the transitions-function \(T\) across the final part of the policy-compliant path \(p_{i}\), cf. (20). This final part consists of the edges \([e^{i}_{l},\ldots,e^{i}_{n}]\), and thus we need to update \(T\) for all edges \((u_{x},u_{y})\) in this partial path. We update \(T\) via the formulae \(T^{\prime}(u_{x},u_{y},q^{i}_{u_{x}},q^{i}_{u_{y}})=T(u_{x},u_{y},q^{i}_{u_{x}},q^{i}_{u_{y}})-c_{f}(p)\) and \(T^{\prime}(u_{x},u_{y},q_{u_{x}},q_{u_{y}})=T(u_{x},u_{y},q_{u_{x}},q_{u_{y}} )+c_{f}(p)\), where we use the notation \(q^{i}_{u_{x}}\) for the state that is reached at vertex \(u_{x}\) when starting in state \(q^{i}_{u_{j}}\) in vertex \(u_{j}\), while \(q_{u_{x}}\) denotes the state that is reached at vertex \(u_{x}\) when starting in state \(q_{u_{j}}\) in vertex \(u_{j}\). After these updates, the augmenting path is processed entirely, and a new iteration can start. Note that, in comparison to the approach for obtaining the first lower bound, condition (20) not only has merits for being more relaxed, it also carries a serious drawback as checking whether condition (20) holds involves more computational work than (16). One possible approach to check whether (20) actually holds, is by a depth-first walkthrough of the realization associated with the flow \(f\). However, this is complicated by the fact that the flow might have multiple valid realizations, some of which are compatible with (20), while some are not. We discuss this now in detail. 1. Consider the augmenting path \(p=[[e_{1},\ldots,e_{i}]\), \([(u_{j},v_{j}),\ldots,(u_{k},v_{k})],[e_{l},\ldots,e_{n}]]\) from above, where the state at \(u_{j}\) is defined as \(q_{u_{j}}=\delta^{*}(q_{0},l(e_{1})\ldots l(e_{i}))\). Suppose there exist two policy-compliant paths \(p_{i}\in P\) and \(p_{j}\in P\), such that their states in vertex \(u_{j}\) are \(q^{i}_{u_{j}}\) and \(q^{i}_{u_{j}}\) respectively. Suppose that the realization of the flow that gave rise to these paths \(p_{i}\) and \(p_{j}\) is such that \(p_{i}=[\ldots,(u_{j},u_{1}),(u_{1},u_{3}),(u_{3},u_{4}),(u_{4},t)]\) and \(p_{j}=[\ldots,(u_{j},u_{2}),(u_{2},u_{3}),(u_{3},u_{5}),(u_{5},t)]\) and moreover that \(l((u_{j},u_{1}))=a,l((u_{1},u_{3}))=b,l((u_{3},u_{4}))=c,l((u_{4},t))=d,l((u_{j },u_{2}))=e\), \(l((u_{2},u_{3}))=f,l((u_{3},u_{5}))=g\) and finally \(l((u_{5},t))=h\) with \(\{a,b,c,d,e,f,g,h\}\subseteq\Sigma\). Then, as \(p_{i}\) and \(p_{j}\) are policy-compliant paths in the set \(P\), it directly follows that \(\delta^{*}(q^{i}_{u_{j}},abcd)\in F\) and \(\delta^{*}(q^{j}_{u_{j}},efgh)\in F\), see Figure 3.
2. Suppose that moreover it holds that \(\delta^{*}(q^{i}_{u_{j}},abgh)\in F\) and \(\delta^{*}(q^{j}_{u_{j}},efcd)\in F\), that is, for the paths \(p_{i}\) and \(p_{j}\) it doesn't really matter which way they take in the second diamond.