# Policy-Compliant Maximum Network Flows
## 4 Policy-Compliant Paths and Algorithms
### First Lower Bound
To identify the vertices involved, suppose that \(e_{j}=(u_{j},v_{j})\) and \(e_{k}=(u_{k},v_{k})\), so \(p=[[e_{1},\ldots,e_{i}],[(u_{j},v_{j}),\ldots,(u_{k},v_{k})],[e_{l},\ldots,e_ {n}]]\), see Figure 2. Starting from state \(q_{0}\), the start state of the automaton, we will reach state \(q_{u_{j}}=\delta^{*}(q_{0},l(e_{1})\ldots l(e_{i}))\) after we crossed all edges \([e_{1},\ldots,e_{i}]\) in the first forward section of the augmenting path. 5. The first forward section of the augmenting path that we have found will be cut at this point, at the cut-vertex \(u_{j}\). For this first approach to obtain a lower bound for the PCMF problem, we assert the overly restrictive constraint that \(\exists u_{y}\in V\) and \(\exists q_{u_{y}}\in Q\) such that \[(u_{j},u_{y})\in E\wedge T(u_{j},u_{y},q_{u_{y}})>0.\] (16)Choose such an edge \(e=(u_{j},u_{y})\in E\) and state \(q_{u_{y}}\in Q\). When the augmenting path \(p\) is cut at vertex \(u_{j}\), we can glue the new flow that comes in via the forward section \([e_{1},\ldots,e_{i}]\) to the flow that leaves vertex \(u_{j}\) in state \(q_{u_{j}}\) via edge \(e=(u_{j},u_{y})\) and reaches state \(q_{uy}\) at the other end in vertex \(u_{y}\). This flow is already available and does not concern us anymore. 6. Now, we need to cancel flow that used to cross the edges \([(v_{k},u_{k}),\ldots,(v_{j},u_{j})]\), that is the backward section of the augmenting path \(p\), crossed in the opposite direction. This gives rise to a second condition for this algorithm to find augmenting paths. This section contains a flow, reaching state \(q_{u_{j}}\) at the end. Tracing back where this flow comes from, we require that there must exist some flow passing vertex \(v_{k}\) in state \(q_{v_{k}}\in Q\) which crosses the edges \([(v_{k},u_{k}),\ldots,(v_{j},u_{j})]\) finally reaching vertex \(u_{j}\) in state \(q_{u_{j}}\). This observation immediately translates to the following condition: \[\exists q_{v_{k}}\in Q:\delta^{*}(q_{v_{k}},l((v_{k},u_{k}))\ldots l((v_{j},u_{ j})))=q_{u_{j}}.\] (17) Choose such a \(q_{v_{k}}\in Q\). Then, the flow that is already present in the network and passes vertex \(v_{k}\) in state \(q_{v_{k}}\) will be canceled over the section \([(v_{k},u_{k}),\ldots,(v_{j},u_{j})]\). 7. We now need to consider the last forward section \([e_{1},\ldots,e_{n}]\). This section starts in vertex \(v_{k}\) and ends in the sink \(t\), thus \(\exists v\in V:e_{l}=(v_{k},v)\) and \(\exists v\in V:e_{n}=(v,t)\). We know that, having reached state \(q_{v_{k}}\) in \(v_{k}\), we will cross edges \([e_{l},\ldots,e_{n}]\) and need to reach some state \(q_{t}\in F\) to obtain a policy-compliant augmenting path. This immediately gives rise to the third and last condition, which can be stated as \[\delta^{*}(q_{v_{k}},l(e_{l})\ldots l(e_{n}))=q_{t}\in F.\] (18)
8. Suppose all conditions (16)-(18) for this augmenting path are fulfilled, which means that we have found an augmenting path that can be joined with the already available policy-compliant paths to increase the total policy-compliant flow. We now need to calculate the amount of flow that can be sent over this augmenting path. First, define \(c_{u_{j}}=min\{c_{f}(u,v):(u,v)\in[e_{1},\ldots,e_{i}]\}\) to be the capacity that is at most available along the first forward section of the augmenting path and thus at the endpoint \(u_{j}\) of this section. Likewise, define \(c_{v_{k}}=min\{c_{f}(u,v):(u,v)\in[e_{l},\ldots,e_{n}]\}\) to be the amount of flow that is at most available along the second forward section of the augmenting path, and thus the maximum amount of flow that can be diverted at the starting point \(v_{k}\) of this section. For the backward section of the augmenting path, define \(c_{v_{k}u_{k}}=T(v_{k},u_{k},q_{v_{k}},q_{u_{k}}),\ldots,c_{v_{j}u_{j}}=T(v_{ j},u_{j},q_{v_{j}},q_{u_{j}})\), to determine the already crossing flow over the backward edges, taking into account the state-transitions which we derived above.