Apr 23, 2026
TCS Seminar – Static and Dynamic Cut-Based Tree Embeddings
Date: April 23, 2026 |
11:30 am –
12:30 pm
Speaker:
Gramoz Goranci, University of Vienna
Location: Moonstone Bldg / Ground floor / Seminar Room G (I24.EG.030g)
Language:
English
Cut-based graph problems are central to combinatorial optimization and theoretical computer science. A powerful algorithmic framework for tackling these problems is cut-based tree embedding, where the goal is to compute a collections of trees that approximately preserves the values of all cuts in any given graph. The seminal work of Rcke (2008), in the context of oblivious routing, showed how to construct such trees with near-optimal quality O(log n). Building on this, Madry (2010) introduced j-tree embeddings to accelerate Rckes construction at the cost of a slightly worse approximation guarantee. These results have been instrumental in the development of near-optimal algorithms for approximating undirected maximum flow.
More recently, the focus has shifted to the dynamic setting, where the challenge is to maintain these embeddings as the underlying graph undergoes edge insertions and deletions. Strikingly, techniques developed for dynamic j-tree embeddings have also become a key ingredient in the recent breakthrough static algorithm for computing maximum flow in directed graphs.
In this talk, I will present the algorithmic constructions underlying static, cut-based tree and j-tree embeddings. Time permitting, I will also discuss some of our recent work on dynamic variants of these objects and their algorithmic applications.
This is based both on prior work by others and on my joint work with Li Chen, Monika Henzinger, Peter Kiss, Ali Momeni, Richard Peng, Thatchaphol Saranurak, and Gernot Zcklein.
More recently, the focus has shifted to the dynamic setting, where the challenge is to maintain these embeddings as the underlying graph undergoes edge insertions and deletions. Strikingly, techniques developed for dynamic j-tree embeddings have also become a key ingredient in the recent breakthrough static algorithm for computing maximum flow in directed graphs.
In this talk, I will present the algorithmic constructions underlying static, cut-based tree and j-tree embeddings. Time permitting, I will also discuss some of our recent work on dynamic variants of these objects and their algorithmic applications.
This is based both on prior work by others and on my joint work with Li Chen, Monika Henzinger, Peter Kiss, Ali Momeni, Richard Peng, Thatchaphol Saranurak, and Gernot Zcklein.
