Lesson 13: Network Algorithms and Approximations by Mohammad Hajiaghayi: Tree Embedding Cut Problems
In this session, we talk about probabilistic tree embedding for cut problems.
The final part of the discussion on oblivious routing and probabilistic embeddings reinforced the core concepts and their theoretical underpinnings. The Oblivious Routing framework dictates finding a set of fixed routes for all source-target pairs such that, regardless of the demands, the resulting network congestion is competitive with the optimal congestion, typically within a log n factor. This theory relies on the decomposition tree, where the capacity of an edge is defined by the minimum cut corresponding to that edge in the original graph. This leads to the central result: the expected relative load (a measure of congestion distortion) of any edge in the probabilistic tree embedding is at most a factor of log n times its capacity in the original graph.
This mathematical machinery is directly applied to solving hard cut problems. A crucial example is the Minimum Bisection Problem, which requires partitioning a graph into two precisely equal halves (n/2 vertices each) while minimizing the cut size. The solution involves finding a set of probabilistic trees, solving the bisection problem optimally on each tree using dynamic programming (a polynomial-time task on trees), and selecting the best result. The domination property ensures that the cost of the solution found in the tree translates directly to a cost in the original graph that is at most the cost in the tree. By showing that the optimal cut in the original graph (OPT) can be embedded into the set of trees, the solution's cost is ultimately bounded by O(log n) times OPT, providing a cleaner and simpler approximation algorithm than previous, highly complex methods.
The lecture also delved into the deep theoretical duality between capacity-based embeddings (Racke's work on cuts) and distance-based embeddings (Bartal/FRT trees on connectivity). This duality, formalized by the min-max theorem, suggests that cut and connectivity problems are fundamentally equivalent in this embedding context. The instructor then previewed the remainder of the course, which will pivot to studying special graph classes, such as planar graphs and sparse graphs. For these classes, the course will move beyond log n approximations to explore Polynomial-Time Approximation Schemes (PTAS), which achieve a 1 + epsilon approximation, demonstrating that superior solutions are possible when the input graph possesses specific structural properties.