Nathan Klein, Institute for Advanced Study

Abstract

 In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This beautiful conjecture, if true, has implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Via a simple reduction technique followed by iterative relaxation, we show that the thin tree conjecture is true for laminar families of cuts. This resolves an open question of Olver and Zenklusen from 2013, a work that showed thin trees exist for chains of cuts. As a byproduct, we also obtain the first constant factor approximation algorithm for the laminar-constrained spanning tree problem with multiplicative violation. Based on joint work with Neil Olver.

See: https://theory.cs.rutgers.edu/theory_seminar