$\exists a_k,k\in [1,i-1],(a_i,a_k)\in G$
### Maximum Integer Flows in Directed Planar Graphs with Multiple Sources and Sinks and Vertex Capacities

<!-- Put the link to this slide here so people can follow -->
Yipu Wang
University of Illinois at Urbana-Champaign

---

## Planar graph

+ Graph can be embedded in the plane without crossing edge
+ Not contain some subgraph homeomorphism with $K_5$ and $K_{3,3}$

----

## vertex capacity

+ Split the the verteces has vertex capacity $C(v)$ to two vertex $v_{in}$,$v_{out}$
+ For edge $(u,v)$ replace the edge with $(u,v_{in})$
+ For edge $(v,u)$ replace the edge with $(v_{out},u)$
+ Build an edge $v_{in}$ to $v_{out}$ with capacity $C(v)$
+ Transform can not keep planar graph ($K_4$)



----

## Multiple Sources and Sinks
+ build super source and super sink connect to all the source and sink
+ transform can not keep planar graph (a $K_4$ sources)
+ There is a $O(nlog^3n)$ algorithm with mutiple sources and sinks in planar graph(algorithm of Borradaile).

---

## problem description

+ $G$ is simple directed plane graph
+ $V(G)$ is vertex set
+ $E(G)$ is edge set
+ $F(G)$ is face set
+ $S$ is sources set
+ $T$ is sinks set
+ terminal vertex is a vertex belong $S$ or $T$
+ Each edge $e$ has capacity $c(e)$
+ Each non-terminal vertex has capacity $c(v)$
+ Find a maximal flow between the $S$ and $T$

---

## related work

###### algorithm of Borradaile


----

## Apex graph
+ $k$-apex graphs is a graph G can be planar after remove at most $k$ vertex
+ The multiple sources and sinks flow on planar can be reduce to single source and sink flow on $2$-apex graph.
+ There is a $O(k^3nlog^3n)$ algorithm with multiple sink and source in $k$-apex graph(algorithm of Borradaile).

----

## vertex Capacity
+ Transform the vertex which has verxtex capacity $C(v)$ to a cycle with edge capactiy $\frac{C(v)}{2}$ and size $in(v)+out(v)$ in clock order, call this garph is $G^。$
 to 

----

Lemma 2.1. Every feasible flow $f$ in $G$ has an extension $f^◦$ that is feasible in $G^◦$.

Lemma 3.1. If $f_{G^。}$ is a plane directed acyclic graph with $k_1$ sources and $k_2$ sinks, then the sum of the indices of the saddles in $f_{G^。}$ is at most $k_1$ + $k_2$ − 2

Lemma 3.2. Let $index(v)$ be defined for each vertex $v$ in $G^。$ using the flow graph $f_{G^。}$ of $f$. For each vertex $v$ in $f_{G^。}$, we have $ex(f, v) \le index(v)c(v)$.

----

###### Lemma 2.1. Every feasible flow $f$ in $G$ has an extension $f^◦$ that is feasible in $G^◦$.

+ According to flow decomposition theorem, If there is a one unit flow into $v$, it can be spit to two $\frac12$ flow in clock and counter-clock dirction in $G^。$, the remain capacity for this vertex is $C(v)-1$ and the vertex cycle has $\frac{C(v)-1}2$ capaicty.


----

For a vertex cycle, merge the adjancency same direction edge.

 to 

+ $\alpha(v)$ is the number of edge in $G_f$ change the direction in clock order in vertex $v$ cycle, is alway even, for the terminal vertex $v'$, $\alpha(v') = 0$.
+ $index(v) = \frac{\alpha(v)}{2} - 1$
+ a vertex $v$ is saddles if $index(v) \ge 1$
+ a vertex is saddles may have excess flow in original graph $G$, its excess flow is $ex(f,v)$.

----

###### Lemma 3.1. If $f_{G^。}$ is a plane directed acyclic graph with $k_1$ sources and $k_2$ sinks, then the sum of the indices of the saddles in $f_{G^。}$ is at most $k_1$ + $k_2$ − 2

+ Each edge connect to two face and two vertex.
+ For a face $\phi$, $\alpha(\phi)$ is the number of adjancency edge change the direciton in clock order.

 make $\alpha(v)$ increase by 1

 make $\alpha(\phi)$ incrase by 1

$2E = \sum_{v\in V(f_G)}\alpha (v) + \sum_{\phi \in F(f_G)} \alpha(\phi)$
$\Rightarrow E = \sum_{v \in V(f_G)}(index(v)+1)+$
$\sum_{\phi \in F(f_G)}(index(\phi)+1)$
$\Rightarrow E=\sum_{v \in V(f_G)}index(v)+\sum_{\phi \in F(f_G)}index(\phi) +$
$V + F$
$\Rightarrow -2\ge\sum_{v \in V(f_G)}index(v)+\sum_{\phi \in F(f_G)}index(\phi)$

since $index(v)=-1$ for each terminal v,
$k_1+k_2-2\ge \sum_{v:index(v)\ge1}index(v)$

----

###### Lemma 3.2. Let $index(v)$ be defined for each vertex $v$ in $G^。$ using the flow graph $f_{G^。}$ of $f$. For each vertex $v$ in $f_{G^。}$, we have $ex(f, v) \le index(v)c(v)$.

+ after we merge the adjancency same direction edge, in the worst case each in edge may carry $c(v)$ unit flow to this vertex, and give half to both adjancency out edge, so total unit of is $c(v)*\frac{\alpha(v)}2 = c(v)*(index(v)+1)$


----

# Bounded integer capcity case

+ For all vertex and edge capacity are integer less than some constant $U$.
+ $f^。$is an integral maximun flow in $G^。$
+ Combine Lemmas 3.1 and 3.2 the sum of the excesses of all vertices in $f^。$ for graph $G$ is at most $(k-2)U$

+ For a infeasible vertex $x$, we remove one unit flow.
+ $f_G$ is the flow graph of $f$
+ Find a path $P_s$ in $f_G$ from $s$ to $x$.
+ Find a path $P_t$ in $f_G$ from $x$ to $t$.
+ The Path $P_s\cup P_t$is a path from s to t, decrease it by 1. And the $ex(f,x)$ also decrease by 1.
+ the algorithm above will take $O(n)$, and we need to remove at most $(k-2)U$ units of flow, total runs in $O(knU)$.

+ And the remaining flow at most $(k-2)*U$, we use Ford-Fulkerson algorithm, it take $O(knU)$
+ Total run time is $O(nlog^3n+knU)$

----

# UnBounded integer capcity case

###### Lemma 3.1. If $f_{G^。}$ is a plane directed acyclic graph with $k_1$ sources and $k_2$ sinks, then the sum of the indices of the saddles in $f_{G^。}$ is at most $k_1$ + $k_2$ − 2
###### There is a $O(k^3nlog^3n)$ algorithm with multiple sink and source in $k$-apex graph(algorithm of Borradaile).

+ For each vectex $v$ has $index(v)\ge 1$, we transform it as above.
+ Use the algorithm of Borradaile.
+ There are at most $k_1+k_2-2$ that node
+ It is $k_1+k_2-2$-apex graph.
+ Total Time complexity is $O(\sum_{i=1}^{k}i^3nlog^3n)\Rightarrow O(k^4nlog^3n)$