Alladi Ramakrishnan Hall

A survey on Flow Augmentation

Sounak Modak

IMSc

In this thesis we study the Flow Augmentation technique which is used to tackle many important graph separation problems in parameterized complexity. The idea of the flow augmentation technique is to take a given graph $G = (V, E)$ with vertices $s, t \in V$ and an unknown $(s, t)$-cut $Z$ (that corresponds to the solution to your problem) and add edges $A$ to $G$ in a way such that with at least probability $1/f(k)$, the new edges $A$ do not interfere with $Z$, and $Z$ is an $(s, t)$-min cut in the resulting graph $G + A$. Here in this thesis we will look into both \textit{"Undirected Flow Augmentation"} and \textit{"Directed Flow Augmentation"} in realm of graph separation problems.