On Element Connectivity Preserving Graph Simplification

Explore a lecture on element-connectivity preserving graph simplification, focusing on a crucial reduction step that maintains element-connectivity in network design and routing problems. Delve into new proofs using setpairs and discover algorithmic advancements for basic element-connectivity problems. Learn about the application of submodularity properties to develop faster algorithms and gain insight into open problems in the field. Examine topics such as packing Steiner trees and forests, internally node-disjoint Steiner trees, and the Cheriyan-Salavatipour Algorithm. Investigate algorithmic aspects, including single pair, all-pair, and global connectivity, as well as approximation techniques in this comprehensive exploration of graph theory and combinatorial optimization.

Intro
Element Connectivity
Motivation/Applications
Rest of the Talk
Packing Steiner trees & forests
Packing internally node- disjoint Steiner trees
Key tool: a graph simplification step
After reduction
Back to packing element- disjoint trees
Cheriyan-Salavatipour Algorithm
Packing bases in polymatroids
Algorithm is same
Packing edge-disjoint Steiner trees
Packing Steiner forests
Packing Elem-Disjoint Steiner forests
Open Problems
Special Case
Switching Topics
Algorithmic Aspects
Single Pair
All-Pair Connectivity
Global Connectivity
A little less naïve algorithm
Finding contractible edge incident to p
Run Times
Approximations