Almost Linear Time Algorithms for Flows in Graphs

Author: Victor Sanches Portella

Supervisor: prof. Marcel Kenji de Carli Silva

We study the main, high-level ingredients of the nearly-linear Laplacian solver of Spielman and Teng and their application to finding an approximately maximum flow in a graph in almost-linear time. We start with basic tools from linear algebra, such as properties of symmetric and positive semidefinite matrices, as well as the Moore-Penrose pseudoinverse. We then move to the Laplacian matrix of a graph and some of its applications, such as computing the number of spanning trees (the so-called Matrix Tree Theorem) and approximating the sparse cuts of a graph.

Next we describe the well-known Conjugate Gradient Method, an iterative algorithm to approximate a solution to a linear system, and use this method with preconditioning to construct an efficient Laplacian solver. In the end, we describe an algorithm to find an approximately maximum flow in undirected graphs in almost-linear time with the help of nearly-linear Laplacian solvers and the multiplicative weights update method.

While the main algorithms covered here are not the fastest known, they contain the majority of the ingredients and tools from the latter.

This work is partially supported by São Paulo Research Foundation (FAPESP) grant nº 2015/24747-3