Untangling near minimum cuts with applications in network design
Presenter
March 30, 2023
Abstract
The structure of the set of global minimum cuts of a graph is well understood and is captured by a cactus, as proved by Dinitz, Karzanov, and Lomonosov in the 70s. However, even for small epsilon, the set of (1+epsilon) near minimum cuts has a significantly more complex structure. Benczúr and Goemans studied near minimum cuts starting in the late 90s and showed that they admit a so-called polygon representation.
In this talk I will show new algorithmically useful properties of this representation and demonstrate two applications in approximating network design problems.