Partially-Dynamic Maximum Flow in Dense Graphs

We are now ready to describe our high-level algorithm (see Algorithm 1). We assume throughout w.l.o.g. that $n$ is a power of $2$ and so are all capacities ⁵⁵5If edge $e$ has capacity $u(e)$ with binary representation $u(e)=2^{r_1}+2^{r_2}+\mathrm{\cdots }+2^{r_p}$, we can split it into at most $\log u(e)=𝒪(\log n)$ edges with capacities $2^{r_1},2^{r_2},\mathrm{\dots },2^{r_p}$.. Our algorithm proceeds in phases. Each edge $e$ is assigned a capacity $\kappa (e)\le u(e)$, which captures the importance of the edge. We use the function $\kappa$ to scale capacities in $G$ down as much as possible, so that a maxflow of value $(1-O(\epsilon ))F$ can still be routed. This results in the corresponding flow being spread out as much as possible, which makes it harder for the adversary to delete it. Initially, we set $\kappa (e)=\frac{1}{n}$ for every edge $e$. Later, we repeatedly double the capacities of some edges. Importantly, we never double the scaled capacity $\kappa$ if the original capacity was achieved, i.e. at all time, for all $e\in E$, we have $\kappa (e)\le u(e)$. Throughout the algorithm, we maintain two sparsifiers: the graph $H_{original}$, which is a cut sparsifier of $G$, and the graph $H_{scaled}$, which is a cut sparsifier of $G$ with scaled capacities $\kappa$. To this end, we use the data structure from Theorem 5 with accuracy $\epsilon$. As $G$ and $\kappa$ undergo updates, so do $H_{original}$ and $H_{scaled}$.

At the beginning of each phase, we run Maxflow$(H_{original},F)$ to ensure that $F^{\ast }(G)\ge (1-O(\epsilon ))F$; if this is not true, we terminate. Otherwise, we call Maxflow$(H_{scaled},F)$ until it returns a flow. If the procedure returns a cut $(S,\overline{S})$, we double capacities $\kappa (e)$ for all edges $e\in E_G(S,\overline{S})$ in the cut with (and therefore $\kappa (e)\le u(e)/2$). Once this process terminates, the algorithm finds a witness flow $f$ to certify that the maximum flow is of value at least $(1-O(\epsilon ))F$. Then, we wait until the adversary deletes edges that carry at least $\epsilon F$ flow in $f$. Once this threshold is reached, we start a new phase.

In our analysis, we assume that the algorithms that maintain $H_{original}$ and $H_{scaled}$ succeed, i.e., the two graphs are $(1-\epsilon )$ cut sparsifiers of the original graphs $G$, and the graph $G$ with capacities $\kappa$ at any time.

We start with the following simple observation.

For our analysis, we introduce the following potential function.

Again, we make some simple observations about the potential.

We have established that the potential starts at $0$ and only increases. We now show that as long as the algorithm does not terminate, it is never too large.

Note that for every flow $f\in ℱ$ we have

where we use $\kappa (e)\le u(e)$ and that all capacities are polynomially-bounded in $n$. Consider next that $f$ is acyclic. Then, we can decompose the flow into flow paths. Clearly, each unit of flow contributes to at most $n-1$ edges at cost at most $O(\log n)$, and thus the cost is bounded from above by $O(F\cdot n\log n)$. Since we can remove cycles from any flow $f\in ℱ$ without decreasing its value and while monotonically removing its cost, we have that some minimizer for $\mathrm{\Pi }(G,\kappa ,F)$ is acyclic. This yields the proposition. $◀$

Next, we bound the increase in potential and total cost of all edges with each scaling $\kappa$.

When a cut $(S,\overline{S})$ is found in Line 12, we have by definition. Since $H_{scaled}$ is a $(1-\epsilon )$ cut sparsifier of $G$ with capacities $\kappa$, we have . Since each edge in $e\in E_G(S,\overline{S})$ has $\kappa (e)$ either doubled (if $\kappa (e)\le u(e)/2$) or unchanged (if $\kappa (e)=u(e)$), we thus have that the increase in $\kappa$ is at most $F$ overall.

We prove the second claim in two steps:

• $\mathrm{■}$

  $𝚷\mathbf{(}𝑮\mathbf{,}𝜿\mathbf{,}𝑭\mathbf{)}$ is finite: In Line 9, the algorithm returned proving that for $H_{original}$, we have that all $s$-$t$ cuts $(S,\overline{S})$ have capacity at least $(1-\epsilon )F$. Since $H_{original}$ is a $(1-\epsilon )$ cut sparsifier of $G$, we thus have

  $$u(E_G(S,\overline{S}))\ge (1-\epsilon )(1-\epsilon )F\ge (1-2\epsilon )F.$$

  Using the max-flow min-cut theorem and Definition 7, $ℱ$ is non-empty and $\mathrm{\Pi }(G,\kappa ,F)$ finite.

• $\mathrm{■}$

  Every flow in $ℱ$ has increased cost: consider any flow $f\in ℱ$. Let $E_{\text{full}}$ be the set of all edges $e\in E_G(S,\overline{S})$ such that $\kappa (e)=u(e)$, and let $E_{\text{double}}=E_G(S,\overline{S})\setminus E_{\text{full}}$, i.e. the edge for which ${\kappa }^{\prime }(e)=2\cdot \kappa (e)$.

  Since the cut was outputted in Line 12, we have that it has capacity in $H_{scaled}$ at most $(1-4\epsilon )F$. Since $H_{scaled}$ is a $(1-\epsilon )$ cut sparsifier of $G$ with capacities $\kappa$, we have

  $$\kappa (E_G(S,\overline{S}))\le (1-3\epsilon )F.$$

  Thus, $E_{\text{full}}\subseteq E_G(S,\overline{S})$ have capacity at most $(1-3\epsilon )F$ under $\kappa$ and since they have $\kappa (e)=u(e)$, we have indeed that $u(E_{\text{full}})\le (1-3\epsilon )F$. Since flow $f$ sends at least $(1-2\epsilon )F$ units of flow, at least $\epsilon F$ units of flow are sent along edges in $E_{\text{double}}$. Since ${\sum }_{e\in E_{\text{double}}}|f(e)|\ge \epsilon F$, we have

  $$c^{\prime }(f)-c(f)=\sum _{e\in E_{\text{double}}}\left(\log (2n\kappa (e))-\log (n\kappa (e))\right)\cdot |f(e)|=\sum _{e\in E_{\text{double}}}|f(e)|\ge \epsilon F.$$

  Therefore, $\mathrm{\Pi }(G,{\kappa }^{\prime },F)\ge \mathrm{\Pi }(G,\kappa ,F)+\epsilon F$.

$◀$

By Lemma 12, every time Maxflow returns a cut, $\mathrm{\Pi }(G,\kappa ,F)$ increases by at least $\epsilon F$. By Proposition 10, this quantity is always $\widetilde{{𝒪}_{\epsilon }}(nF)$, so the number of such increases is at most $\widetilde{{𝒪}_{\epsilon }}(n/\epsilon )$. By Lemma 12, every call of Maxflow that returns a cut incurs increases in $\kappa (E_0)$ by at most $F$, so in the end we have $\kappa (E_0)=\widetilde{{𝒪}_{\epsilon }}(nF)$. $◀$

Denote the set of all deleted edges by $E_{\text{del}}$ and consider the quantity $\kappa (E_{\text{del}})={\sum }_{e\in E_{\text{del}}}\kappa (e)$. We begin a new phase only when the counter Flow-Deleted exceeds $\epsilon F$, so the total number of phases is bounded by $\kappa (E_{\text{del}})/(\epsilon F)$. Using $\kappa (E_{\text{del}})\le \kappa (E_0)$, that fact that initially $\kappa (E_0)$ is $|E_0|\cdot \frac{1}{n}\le O(n)$ and Corollary 13, we obtain

$◀$

It remains to analyze the runtime. Before we delve into the full analysis, we still need to clarify an implementation detail: when the Maxflow algorithm is executed in Line 12 terminates with a cut $(S,\overline{S})$, it subsequently requires enumerating the edges in $E_G(S,\overline{S})$. Notably, it finds the cut in the graph $H_{scaled}$. We use the following fact.

We use a dynamic connectivity data structure as given in [24]. Such data structures maintain a maximal spanning forest $F$ of the current graph, which can be stored efficiently in a dynamic tree data structure such as [4].

Consider now any vertices $u\in S,v\in \overline{S}$ and the $u$-$v$ path $F[u,v]$ along $F$. Via the dynamic tree data structure, one can efficiently query the midpoint $x$ on $F[u,v]$ (ties broken arbitrarily). Since we can check efficiently if $x\in S$, we set $u=x$; otherwise, we set $v=x$. Then, we recurse again on $F[u,v]$. It is not hard to verify that after $O(\log n)$ such steps, $(u,v)$ is an edge in $E_G(S,\overline{S})$.

To enumerate the cut, we use the above process, then delete the edge $(u,v)$ from $G$. This yields for an adapted forest $F$ that does not use edge $(u,v)$ and thus yields a new edge upon repeating this process. Upon finding all edges in $E_G(S,\overline{S})$ via this process, we simply add the deleted edges back into the connectivity data structure. The tree data structure can also be used to remove vertices $u\in S$ that are not connected to any vertex in $\overline{S}$ or otherwise return a vertex $v\in \overline{S}$ in the same connected component.

Since the connectivity data structure and dynamic tree data structure support all of the above operations in $\widetilde{{𝒪}_{\epsilon }}(1)$ time, the claimed runtime is achieved. $\mathrm{⊲}$

Finally, we are ready to prove Lemma 4.

We argue correctness first. Algorithm 1 terminates only if Maxflow returns a cut in Line 9. This means that . Since $F^{\ast }(G)\le F^{\ast }(H_{\text{original}})$, we get .

On the other hand, the initialization of a new phase terminates after the Maxflow procedure in Line 12 certifies that an $s$-$t$ flow of value at least $(1-\epsilon )(1-3\epsilon )F\ge (1-4\epsilon )F$ can be routed in $H_{scaled}$ and thus at least $(1-\epsilon )(1-4\epsilon )F\ge (1-5\epsilon )F$ flow can be routed in $G$ with capacities $\kappa$.

Since throughout a phase, edges of total scaled capacity $\kappa$ at most $\epsilon F$ are deleted, we have that at least $(1-5\epsilon )F-\epsilon F=(1-6\epsilon )F$ flow remaining, as desired.

Finally, we argue about the time complexity. In particular, we need to bound the cost of max-flow calls and the subroutine for enumerating cut edges. All other costs are subsumed by these bounds. To this end, we observe that any edge that was enumerated in a cut has its capacity thereafter doubled, and thus appears at most $O(\log n)$ times in such cuts. Since by Corollaries 14 and 13, the number of Maxflow calls and cut enumerations is $\widetilde{{𝒪}_{\epsilon }}(n)$, and since Maxflow calls run in time linear in the number of edges of the cut sparsifiers that they run on, we obtain total runtime $\widetilde{{𝒪}_{\epsilon }}(n^2)$. $◀$

For every node with interval $I=[a,b)$ we store a $(1-{\epsilon }_0)$ cut sparsifier $H_I$ of $G_I$.

Upon receiving $E_i$, we set the leaf structure for $[i,i+1)$ (e.g. $H_{[i,i+1)}:=(V,E_i)$), and then update the nodes on the path to the root. For a parent interval $I=I_L\cup I_R$ we set

where $\cup$ denotes weighted union (we assume that weights add on duplicates).

Fix a cut $S\subseteq V$. By assumption, for each $i\in \{1,2\}$ we have

Adding the two inequalities and using $u(E_G(S,\overline{S}))=u(E_{G_1}(S,\overline{S}))+u(E_{G_2}(S,\overline{S}))$ and $u^{\prime }(E_H(S,\overline{S}))=u^{\prime }(E_{H_1}(S,\overline{S}))+u^{\prime }(E_{H_2}(S,\overline{S}))$, we obtain

$◀$

Now set ${\epsilon }_0=\mathrm{\Theta }(\epsilon /\log k)$. Since each $H_{[a,b)}$ is produced by at most $\log k$ applications of Sparsify along a root-to-leaf path, the total distortion accumulates multiplicatively: for every cut $S$,

Choosing the hidden constant in $\mathrm{\Theta }(\cdot )$ appropriately yields

Together with Proposition 17, this leads to the following result.

The time complexity of maintaining the segment tree is straightforward. The tree has $k$ leaves and at most $2k-1$ nodes. By the invariant, each stored sparsifier has $\widetilde{{𝒪}_{\epsilon }}(n)$ edges, so each merge

takes $\widetilde{{𝒪}_{\epsilon }}(n)$ time. Each update triggers $𝒪(\log k)$ merges along the path to the root, hence the total time over $k$ updates is $𝒪(nk\log k)=\widetilde{{𝒪}_{\epsilon }}(nk)$.

Now consider any interval $[a,b)$. It can be decomposed (in the standard way) into a disjoint union of at most $\log k$ intervals $I_1,\mathrm{\dots },I_s$ associated with tree vertices. Then we let $H_{[a,b)}={\bigcup }_{j=1}^s{H}_{I_j}$ (with weighted union). Finally, when we are asked for a sparsifier for the graph $G_{[0,a)}$ for some $a$, we return the graph $H_{[0,a)}$, which is a $(1-\epsilon )$ cut sparsifier of $G_{[0,a)}$ by Propositions 17 and 18.

Our data structure also needs to maintain a maximum flow for every prefix sparsifier $H_{[0,a)}$. To do so, for every tree node with interval $[a,b)$ we additionally store a flow $f_{[a,b)}$.

For every prefix $[0,a)$ with canonical decomposition

define the flow $f_{[0,a)}$ by

Then $f_{[0,a)}$ is a maximum $s$–$t$ flow in the graph $H_{[0,a)}$.

Let $[a,b)$ be a node that is the left child of its parent, and let $[0,a)$ be the prefix interval corresponding to all time indices strictly before $a$. Denote by $R_{[0,a)}$ the residual network of $H_{[0,a)}$ with respect to the flow $f_{[0,a)}$. Then the stored flow $f_{[a,b)}$ is a maximum $s$–$t$ flow in the graph $R_{[0,a)}\cup H_{[a,b)}$.

Upon receiving $E_b$ (thus initializing the leaf $[b,b+1)$), we update the flows for nodes affected by the segment-tree update. In particular, for every node of the form $[a,b+1)$ that is a left child, we compute a maximum flow in the graph

where $R_{[0,a)}$ is the residual network of $H_{[0,a)}$ with respect to $f_{[0,a)}$. Together with the flow $f_{[0,a)}$, this yields a maximum flow in

To compute each maximum flow $f_{[a,b)}$ we use the Ford–Fulkerson algorithm on the graph $R_{[0,a)}\cup H_{[a,b)}$.

Let us next bound the runtime of this procedure.

Fix a node $[a,b)$. The graph on which we compute $f_{[a,b)}$ is of the form $R_{[0,a)}\cup H_{[a,b)}$. By construction, every sparsifier stored in the tree has $\widetilde{{𝒪}_{\epsilon }}(n)$ edges, and the residual network adds at most a $\log k$ factor more edges. Hence $R_{[0,a)}\cup H_{[a,b)}$ has $\widetilde{{𝒪}_{\epsilon }}(n)$ edges.

We compute $f_{[a,b)}$ using the Ford–Fulkerson algorithm. Under our capacity model, each augmentation increases the flow value by at least one unit, and each augmentation can be found in time linear in the number of edges. Therefore, the time to compute $f_{[a,b)}$ is

Thus it suffices to bound ${\sum }_{[a,b)}\mathrm{val}(f_{[a,b)})$ over all nodes in the tree.

We prove the following stronger statement by induction on the interval length $(b-a)$. Let

Then

$b-a=1$. Then the subtree contains only the node $[a,a+1)$, and by definition

Let $m=(a+b)/2$, and let $L=[a,m)$ and $R=[m,b)$ be the left and right children. By the induction hypothesis applied to $L$ and $R$,

Since $m-a=b-m=(b-a)/2$, we have $\log (m-a)+1\le \log (b-a)$ and $\log (b-m)+1\le \log (b-a)$.

Moreover, by definition,

Finally, since $R_{[0,m)}$ is the residual network after sending a maximum flow in $H_{[0,m)}=H_{[0,a)}\cup H_L$, the additional maximum flow obtainable after adding $H_R$ satisfies

Combining these bounds, we obtain