Title: Max-flow min-cut gap in node-capacitated networks

Abstract:
In edge capacitated networks, the ratio between the maximum flow and the minimum cut in multi-commodity flows is well-studied and it is known that this ratio is tightly connected to the minimum distortion required for embedding of the metrics supported on the graph into L1.
However, for node capacitated networks and vertex separators such a relationship between L1 embeddings and flow/cut gap does not exist.  Feige Hajiaghayi and Lee used a stronger notion of embedding to bound the flow/cut gap in node-capacitated graphs. In this talk, we will discuss a new approach that generalizes the techniques from Feige Hajiaghayi and Lee. In a recent work with Lee and Mendel, we introduced this approach to answer an open question of Chekuri, Kawarabayashi, and Shepherd, and prove a node-capacitated version of Okamura-Seymour theorem.