Thin trees for laminar families
Neil Olver ( London School of Economics )
- 14:00 15th February 2024 ( week 5, Hilary Term 2024 )Seminar Room 051
Given a k-edge-connected graph, can we always find a spanning tree containing at most an O(1/k) fraction of the edges across every cut? This so-called thin-tree conjecture, if true, has several implications for problems in graph theory and approximation algorithms. A natural relaxation of this problem is to find a spanning tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. We give a surprisingly simple and constructive proof that this relaxed conjecture holds for any laminar family of cuts, based on iterative rounding.
Joint work with Nathan Klein.
Share this:
