Advanced Algorithms UE 4

by Maarten Behn
Group 5

Exercise 4.1

a) Give an example of a network $\mathcal{N}$ in which $|V|\le 4$ and the number of iterations of the Ford-Fulkerson Algorithm is $c_{max}$, where $c_{max}$, is the largest capacity of any arc.
b) What is the size of the input for this example?
c) Prove that this leads to an exponential running time (w.r.t. the size of the input).

a)

Transclude of AA-UE-4.1.1.excalidraw

$m\in \mathbb{N}$ and therefore $m=c_{max}$
$\mathbb{N}:=\mathbb{N}\backslash \{0\}$

Example for $m=2$

“Worst” paths

If the Algorithm always happens to choose the path over the center edge
the algorithm takes $2\cdot m$ Iterations.

Transclude of AA-UE-4.1.2.excalidraw

Ford-Fulkerson always choose an path over the center edge.

The incoming flow to t is increaes by one for every iteration.
t has an incoming flow of $2\cdot m$. Therefore Ford-Fulkerson takes up to $2\cdot m$ iterations for this exmaple.

Proof that Ford-Fulkerson always choose an path over the center edge.

Ford-Fulkerson repeatly chooses s-2-1-t and s-1-2-t.
After every s-2-1-t path 1-2 has a capacity of 1 and s-1-2-t can be choosen next.
After every s-1-2-t path 2-1 has a capacity of 1 and s-2-1-t can be choosen next.

$2\cdot m\le c_{max}$

b)

Use the Graph from a) to construct:

Transclude of AA-UE-4.1.4.excalidraw

The input size is $m\cdot n$

c)

I proved in a) that Ford-Fulkerson can take up to $2\cdot m$ Iterations for a sub graph $G$.
In the Graph of b) consist of $n$ Sub graphs of a).

Therfore the $G$ of b) has $|A|=5\cdot n$ edges.

In the Lecture the runtime of Ford-Fulkerson is $O(|A|\cdot M)$ with $M$ value of maximum flow.
For $G$ of b) $M=2\cdot n\cdot m$

Therfore $G$ of b) has a Runtime of
$O\left(5\cdot n\cdot 2\cdot n\cdot m\right)=O\left(n^2\cdot m\right)$

which corresponds to a Runtime of
$O\left({\left(\frac{|A|}{5}\right)}^2\cdot c_{max}\right)=O\left(|A{|}^2\cdot c_{max}\right)$

Exercise 4.2

Let $f$ be a flow in a network $\mathcal{N}=(V,E,c,s,t)$, and let $g$ be a flow in the residual network ${\mathcal{N}}_f$ of $\mathcal{N}$ w.r.t. $f$.
Prove the following statements:
a) $f+g$ is a flow in $\mathcal{N}$.
b) If $g$ is a maximum flow in ${\mathcal{N}}_f$ , then $f+g$ is a maximum flow in $\mathcal{N}$.

a)

Define the sum of flows as $t=f+g$
$t(u,v)=f(u,v)+g(u,v)-g(v,u)$
and
$c_t(u,v)=c(u,v)-f(u,v)$

capacity constraints

For $u,v\in Vu\ne v$

show that
$0\le t(u,v)\le c(u,v)$

since $f(u,v)\le c(u,v)$ and $g(u,v)\le c_t(u,v)$
$f(u,v)+g(u,v)\le c(u,v)$

since $g(v,u)\le 0$
$f(u,v)+g(u,v)-g(v,u)\le f(u,v)+g(u,v)$

$t(u,v)\le c(u,v)$

since $f(u,v)\ge 0$ and $g(v,u)\le f(u,v)$ (there is only an backwards residual egde if there is a flow $f(u,v)>0$)
$t(u,v)\ge f(u,v)-g(v,u)\ge 0$

flow conservation

For $v\in V\backslash \{s,t\}$

since $f$ and $g$ hold the flow conservation
$\sum _{u}f(u,v)=\sum _{u}f(v,u)$
$\sum _{u}g(u,v)=\sum _{u}g(v,u)$

$\sum _{u}t(u,v)=\sum _{u}f(u,v)-\sum _{u}g(u,v)-\sum _{u}g(v,u)=\sum _{u}f(u,v)-\sum _{u}g(u,v)-\sum _{u}g(u,v)=\sum _{u}f(u,v)$

b)

Since $f+g$ is a flow → a)

Proof by contradiction

Suppose that $t$ is not a maximum flow in $N$. Then, there exists some flow $h$ in $N$ such that $|h|>|f+g|$
$|h|-|f|>|f+g|-|f|=|g|$
this is a contradiction with $g$ being maximum.

Since $g$ is a maximum flow in the residual network $N_f$, the Optimality criteria Theorem says:
The residual network $N_f$ ​ has no augmenting s-t-paths.

Hence, by the Max-Flow Min-Cut Theorem, $t$ is a maximum flow in $N$.

Exercise 4.3

Let $N=(V,E,c,s,t)$ be an s-t-network with $m$ edges.
Prove that there exists a maximum flow in N that is the sum of at most m flows $f_1,...,f_k$, each of which takes positive values only on a single s-t-path in $N$ .
Moreover, prove that if all capacities in $N$ are integers, then $f_1,...,f_k$ can be chosen as integral flows.

Proof by induction

Assumption

$f=\sum _{i=0}^k{f}_i+\sum _{i=0}^n{c}_i$
where

1. $f_i$ is either an s-t-path and $c_i$ an flow cicle. This means only the edges on the path or cicle have positive value.
2. $k\le |E|$
3. $f_i$ is an integral flow when $f$ is an integral flow.

Step repeat while $|f^{\prime }|\ne 0$

Define a residual graph $G_f$ based on $f^{\prime }$
$G_f$ contains only edges with a positive flow $f^{\prime }(e)>0$

Pick an vertex $v$ with an non zero incoming flow.
Search for an s-t-path $P$ covering $v$.
If there is no path then there must be a circle $C$ that covers $v$.

$\delta =min{}_{e\in \text{P or C}}{f}^{\prime }(e)$

Construct a new flow $f_P$ or $f_C$ from $P$ or $C$ where the value of all edges is $\delta$
$f^{\prime }:=f^{\prime }-f_P\text{or}{f}_C$

Proof $k\le |E|$

There can be at most $|E|$ s-t-paths in $G$
And there is no path $f_a,f_b$ that are equal, because the edge with the minimum capacity is has a capacity of zero after the path of $f_a$ is found.

Proof $f_i$ is an integral flow when $f$ is an integral flow.

If $f$ is intigral $\delta$ is always intigral therefore $f_i$ is intigral.

Source:
https://theory.stanford.edu/~trevisan/cs261/lecture11.pdf (11.05.‘25 17:20)