# Policy-Compliant Maximum Network Flows
## 4 Policy-Compliant Paths and Algorithms
### Second Lower Bound  
Although the approach described above results in correct lower bounds for the policy-compliant maximum flow problem, we point out that the conditions (16)-(18) that are imposed upon augmenting paths are very restrictive. Indeed, it is easy to describe specific cases where the approach misses additional augmenting paths due to these conditions, which can easily be relaxed at the expense of additional computational work. The next approach, which will result in a second lower bound that is tighter than the first bound, starts by relaxing condition (16). In its essence, this condition says that for an augmenting path, containing a backward section, it is necessary to glue the immediately previous forward section to a pre-existent policy-compliant path at the cut-vertex, via an exact match of the state in that cut-vertex. Clearly, this is too restrictive a condition as it would be sufficient if the augmenting flow arriving at that vertex could be continued via the same edges, however taking different intermediate states in between. 1. To make this formal, consider the augmenting path \(p=[e_{1},\ldots,e_{n}]\) where \(e_{i}\in E_{f}\), which may 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\). For simplicity, we once more 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}\). To identify the vertices involved, say 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}]]\). The state at \(u_{j}\) is defined as \(q_{u_{j}}=\delta^{*}(q_{0},l(e_{1})\ldots l(e_{i}))\). 2. For flow \(f\), suppose that the policy-compliant paths \(P=\{p_{1},\ldots,p_{n}\}\) are the part of the realization of \(f\) that crosses \(u_{j}\). Thus, \(\forall p_{i}\in P:\exists v_{i}\in V:(u_{j},v_{i})\in p_{i}\). For each of these policy-compliant paths \(p_{i}\), the state upon arriving in \(u_{j}\) is denoted by \(q^{i}_{u_{j}}\). Moreover, there might be more than one path \(p_{i}\in P\) that arrives in \(u_{j}\) with state \(q^{i}_{u_{j}}\), that is for some \(i\) and \(j\) it might be the case that \(i\
eq j\) and \(q^{i}_{u_{j}}=q^{i}_{u_{j}}\). The amount of flow that policy-compliant path \(p_{i}\) carries is denoted by \(c_{i}\), thus \(\forall p_{i}\in P:(p_{i},c_{i})\in S\), cf. (11). 3. Now, instead of stating in the first condition (16) that there must be a policy-compliant path \(p_{i}\in P\) such that \(q_{u_{j}}=q^{i}_{u_{j}}\) with \(c_{i}>0\) it is, in fact, sufficient that there exists a path \(p_{i}\in P\) such that following the rest of the policy-compliant path \(p_{i}\) after crossing \(u_{j}\) results in a final state at the sink \(t\) even though \(q_{u_{j}}\
eq q^{i}_{u_{j}}\). More formally, if \(p_{i}=[e^{i}_{1},\ldots,e^{i}_{k^{\prime}}e^{i}_{l},\ldots,e^{i}_{n}]\) such that \(e^{i}_{k}=(u_{x},u_{j})\) and \(e^{i}_{l}=(u_{j},u_{y})\) for some \(u_{x}\in V\) and \(u_{y}\in V\), then it is sufficient to impose, instead of (16), simply that \[\exists p_{i}\in P:\delta^{*}(q_{u_{j}},l(e^{i}_{l})\ldots l(e^{i}_{n}))\in F.\] (20) Choose such a \(p_{i}\in P\). That way, we are confident that the prefix \(l(e_{1})\ldots l(e_{i})\) can be joined together with a suffix \(l(e^{i}_{l})\ldots l(e^{i}_{n})\) such that for the whole word holds that \(\delta^{*}(q_{0},l(e_{1})\ldots l(e_{i})l(e^{i}_{1})\ldots l(e^{i}_{n}))\in F\). 4. At this point, we have to be careful which policy-compliant flows crossing the backward section \([e_{j},\ldots,e_{k}]\) we are going to cancel.