The classical Max-Flow Min-Cut theorem by Ford and Fulkerson states that the maximum flow between two vertices, s and t, in a graph is equal to the minimum capacity of a set of edges whose removal disconnects s from t. This is a central theorem on which the theory of flows and cuts is based and holds a central place in algorithms and discrete optimization.

 

In this talk, I will discuss generalizations of this theorem to the multicommodity setting, where we have multiple source-sink pairs instead of one. Unfortunately, in the multicommodity setting, we cannot achieve an exact Max-Flow Min-Cut result and must settle for approximate ones. There is a rich and impressive body of work dedicated to proving such results, driven by their importance in designing approximation algorithms. I will discuss recent developments in this area and highlight some key open problems.

 

Short Bio: Nikhil Kumar is a postdoctoral researcher in the Department of Combinatorics and Optimization at the University of Waterloo. He earned his bachelor's, master's, and Ph.D. in Computer Science and Engineering from IIT Delhi. His broad area of interest is approximation algorithms and combinatorial optimization, with particular emphasis on network problems.