## Invited Session Fri.3.H 3013

#### Friday, 15:15 - 16:45 h, Room: H 3013

**Cluster 2: Combinatorial optimization** [...]

### Flows, cuts, and sparsifiers

**Chair: Nicholas Harvey**

**Friday, 15:15 - 15:40 h, Room: H 3013, Talk 1**

**Nicholas Harvey**

Graph sparsifiers

**Abstract:**

A sparsifier of a graph is a sparse, weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of *1 ± ε*. Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging applications, including fast network flow algorithms, fast linear system solvers, etc.

We describe a new approach to constructing sparsifiers: by sampling each edge *uv* with probability inversely proportional to the edge-connectivity between *u* and *v*. This results in a sparsifier with *O(n **log*^{2}(n) / ε^{2}) edges, answering a question of Benczur and Karger. A variant of this argument shows that one can obtain sparsifiers by sampling uniformly random spanning trees. Our proofs are based on extensions of Karger's contraction algorithm which allow it to compute minimum "Steiner'' cuts.

**Friday, 15:45 - 16:10 h, Room: H 3013, Talk 2**

**Jonathan Kelner**

Electrical flows, linear systems, and faster approximations of maximum flows, minimum *s*-*t* cuts, and multicommodity flows in undirected graphs

**Coauthors: Paul Christiano, Aleksander Madry, Gary Miller, Richard Peng, Daniel Spielman, Shanghua Teng**

**Abstract:**

\def\e{ε}

\def\p{\mathrm{poly}}

\def\o{Õ}

In this talk, I'll describe a new collection of techniques for approximately solving maximum flow, minimum *s*-*t* cut, and multicommodity flow problems in capacitated, undirected graphs. Using these techniques, we obtain asymptotically faster algorithms for all three, breaking running time barriers that have stood for over 30 years.

For graphs with *n* vertices and *m* edges, I'll show how to compute *\e*-approximately maximum flows in time *\o(m*^{4/3})\p(1/\e) and *\e*-approximately minimum *s*-*t* cuts in time *\o(m+n*^{4/3})\p(1/\e). We do this by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time.

I'll then discuss why generalizing this approach to the multicommodity setting requires more general classes of linear systems and iterative methods. Using these, we find *\e*-approximate solutions to the maximum concurrent flow problem with *k* commodities in time *\o(m*^{4/3}\p(k,\e^{-1})).

**Friday, 16:15 - 16:40 h, Room: H 3013, Talk 3**

**Christophe Weibel**

When the cut condition is enough: Characterization of multiflow problems by forbidden minors

**Coauthors: Amit Chakrabarti, Lisa Fleischer**

**Abstract:**

For a supply graph *G=(V,E)* and a demand graph *H=(V,F)*,

an assignment of capacities to the

edges of *G* and demands to the edges of *H* is said to satisfy the

*cut condition* if for any cut in the graph, the total demand

crossing the cut is no more than the total capacity crossing it.

The pair *(G,H)* is called *cut-sufficient* if for any

assignment of capacities and demands that satisfy the cut condition,

the demands defined on *H* can be routed within the

network with capacities defined on *G*.

A pair *(G, H)* is said to contain another pair *(G', H')* as a minor

if it is possible to obtain *(G', H')* from *(G, H)* by contracting

edges of *G* and deleting edges of *G* and *H*. We propose

to characterize cut-sufficient pairs by forbidden minors.

In particular, we prove a previous conjecture giving the minimal set of forbidden minors

for instances with a series-parallel supply graph, and propose a

conjecture extending our results to planar supply graphs.