## Seminars on Graph Algorithms: Alksander Mądry (EPFL) , Jakub Łącki (Univ. of Warsaw), Dariusz Leniowski (Univ. of Warsaw)

+++++++++++++++++++++++++++++++++++**Speaker**: Alksander Mądry (EPFL)**Title**: Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back**Abstract**:

We describe a new way of employing electrical flow computations to solve the maximum flow and minimum s-t cut problems. This approach draws on ideas underlying path-following interior-point methods (IPMs) – a powerful tool in convex optimization - and exploits certain interplay between maximum flows and bipartite matchings.

The resulting algorithm provides improvements over some long-standing running time bounds for the maximum flow and minimum s-t cut problems, as well as, the closely related bipartite matching problem. Additionally, we establish a connection between primal-dual structure of electrical flows and convergence behavior of IPMs when applied to flow problems. This connection enables us to overcome the notorious Omega(sqrt(m))-iterations convergence barrier that all the known interior-point methods suffer from.

++++++++++++++++++++++++++**Speaker**: Jakub Łącki (Univ. of Warsaw)**Title**: Dynamic Steiner Tree **Abstract**:

We study the Steiner tree problem over a dynamic set of terminals. We

consider the model where we are given an n-vertex graph G with

nonnegative edge weights. Our goal is to maintain a tree T which is a

constant approximation of the minimum Steiner tree in G, as the set of

terminal vertices changes over time. The changes applied to the

terminal set are terminal additions or removals. We obtain a

polylogarithmic time algorithm for dynamic Steiner tree in planar

graphs and a sublinear one for general graphs. We also show that after

each operation a small number of changes to the tree (in amortized

sense) suffices to maintain a (2+epsilon)-approximate Steiner tree.

This is joint work with Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski and Anna Zych.

++++++++++++++++++++++**Speaker**: Dariusz Leniowski (Univ. of Warsaw)**Title**: Online bipartite matching in offline time**Abstract**:

We present an alternative method for constructing augmenting-path algorithms and demonstrate it using bipartite matchings. The resulting algorithm is able to maintain maximum cardinality bipartite matching in one-sided online fashion in total time of O(mn^{1/2}), i.e., the same as the offline Hopcroft-Karp algorithm. The resulting procedure is very simple and uses just one graph search algorithm DFS or BFS. Moreover, our approach has a number of desirable properties that, depending on the context, could make it a preferred choice even in the offline setting. Besides introducing the algorithm and the intuition behind it, the talk will outline the major lemmas and sketch the non-technical parts of the proof.

This is joint work with Bartłomiej Bosek, Piotr Sankowski and Anna Zych.