Nathan Klein, Boston University

Abstract

We show that every fractionally k-edge-connected weighted graph (i.e. every solution to the canonical k-edge-connectivity linear program) can be rounded to an integral (k-10)-edge-connected graph of no greater cost.

This implies that for large constant values of k, fractional k-edge-connectivity and integral k-edge-connectivity are essentially the same. As a byproduct of this result, we show that one can produce a (k-10)-edge-connected spanning subgraph (ECSS) of cost no more than the optimal k-ECSS, complementing the existing 2-approximation. This result also implies a 1+O(1/k) approximation for the k-edge-connected multi-subgraph problem (k-ECSM), resolving a conjecture of Pritchard from 2011.

This is joint work with Ellis Hershkowitz and Rico Zenklusen.

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