# Policy-Compliant Maximum Network Flows
## 4 Policy-Compliant Paths and Algorithms
### First Lower Bound  
To cut down on the needed computational resources, we start from the classic Ford-Fulkerson or Edmonds-Karp algorithm. In its essence, these algorithms start with an empty flow, after which a new augmenting path is looked for in the residual graph. If found, this augmenting path gives rise to an augmented flow, after which the residual graph is updated. Then, a new iteration is started. Once no new augmented paths can be found, the algorithm has reached the maximum flow. In order to apply this approach to the policy-compliant maximum flow problem, it will be necessary to keep track of how the flow actually is realized, throughout the execution of the algorithm. This relates to the fact that flows cannot merge and split anonymously anymore, as discussed previously. As a first step, it will be necessary to keep track of the different state-transitions that occur when flow crosses an edge \(e=(u,v)\in E\) in a path \(p\) and changes state during that transition from state \(q_{u}\in Q\) in vertex \(u\) to state \(q_{v}\in Q\) in vertex \(v\). To that aim, we define transitions \(t\) to be members of the set \(Q\times Q=\{(q_{u},q_{v}):q_{u}\in Q\wedge q_{v}\in Q\}\). For every edge \(e\in E\) we will now keep track of all transitions that cross that edge, and thus define the total function \(T:V\times V\times Q\times Q\rightarrow\mathbb{R}\). This function keeps track of the amount of flow that crosses the edge \((u,v)\) while changing state from \(q_{u}\) to \(q_{v}\) as the value \(T(u,v,q_{u},q_{v})\). As a direct consequence, we have at all times \(\forall u,v\in V:\sum_{q_{u},q_{v}\in Q}T(u,v,q_{u},q_{v})=f(u,v)\leq c(u,v)\) which expresses the fact that a flow over an edge can be split up in different transitions, the amount of which add up exactly to the amount of flow crossing that very edge. Keeping track of this function \(T\) allows the algorithm to discriminate between the different states in one single vertex, and the amount of the flow that is actually passing through that vertex having that state at that moment. This information is then used to glue together already found policy-compliant paths and a newly found augmenting path. In detail, this procedure works as follows. 1. Beginning with a labeled network \(G\) and a FSA \(M\), we start a new flow and set \(f(u,v)=0\) for all vertices \(u\) and \(v\). Moreover, we set \(T(u,v,q_{u},q_{v})=0\) for all vertices \(u,v\in V\) and all states \(q_{u},q_{v}\in Q\). 2. Finding the first policy-compliant augmenting path can be straightforwardly done. Indeed, as the residual graph \(G_{f}\) is still the same as the original graph \(G\) (because \(\forall u,v:f(u,v)=0\)), the augmenting path that is found in the first iteration will be a path containing only forward sections. The flow is then updated according to (9). 3. From the second iteration on, we need to take into account the reverse edges in the residual graph with great care. Now, it is not sufficient anymore to simply look for policy-compliant paths containing only forward sections, as an augmenting path may now contain reverse edges from the residual graph. In general, we will look for an augmenting path \(p=[e_{1},\ldots,e_{n}]\) where \(e_{i}\in E_{f}\), that can have multiple forward and backward sections, and which can thus be split as \(p=[[e_{1},\ldots,e_{i}],[e_{j},\ldots,e_{k}],\ldots,[e_{l},\ldots,e_{n}]]\), such that each section \([e_{x},\ldots,e_{y}]\) only contains edges from either \(E\) or \(E_{f}-E\). We will now determine the constraints that are to be applied to ensure that the newly found augmenting path \(p\) can be split up and glued together with other policy-compliant paths that are already part of the flow \(f\). 4. For simplicity, we discuss the case where the augmenting path \(p\) consists of two forward sections with one backward section in between, that is \(p=[[e_{1},\ldots,e_{i}],[e_{j},\ldots,e_{k}],[e_{l},\ldots,e_{n}]]\) such that \(\{e_{1},\ldots,e_{i},e_{l},\ldots,e_{n}\}\subseteq E\) and \(\{e_{j},\ldots,e_{k}\}\subseteq E_{f}-E\).