Lesson 16: Network Algorithms and Approximations by Mohammad Hajiaghayi: Simplifying Decompositions

Описание: In this session, we talk about different simplifying decompositions for networks and their applications to obtain approximation algorithms, in particular PTASs, and fixed parameter algorithms. The lecture contrasted the Separator Decomposition approach (Lipton-Tarjan, generalized by Bidimensionality), which finds small separators to recursively break down a graph, with the Simplifying Decomposition approach (Baker), which is more suitable for problems involving weights and non-minor-closed properties. The core idea of simplifying decomposition is to partition the graph's vertices or edges into a small number of pieces (K pieces, where K is typically proportional to 1 divided by epsilon), such that deleting or contracting any single piece leaves the remaining subgraph with bounded treewidth. Since all problems are efficiently solvable on graphs of bounded treewidth, this technique is a powerful tool for obtaining PTAS results.

The instructor presented a key theorem: any H-minor free graph can have its vertices or edges partitioned into K pieces such that removing any one piece results in a bounded treewidth graph. This structure immediately yields powerful results, like a two-approximation for the highly difficult Chromatic Number problem on H-minor free graphs. By partitioning the vertices into two sets, each with bounded treewidth, the problem is solved optimally on each set, and the results are combined by using a new set of colors, achieving a two times the chromatic number of the graph approximation. More importantly, using an edge-partitioning version of the theorem with K approximately equal to 1 divided by epsilon pieces allows for a PTAS for problems like Max Cut on H-minor free graphs, despite Max Cut being APX-hard on general graphs.

For problems like the Traveling Salesperson Problem (TSP), which is contraction-closed but not minor-closed, the more specialized Contraction Decomposition Theorem is required. This theorem partitions the edges into K sets such that contracting any one set results in a bounded treewidth graph. The algorithm uses this structure on a spanning subgraph (spanner) of the original graph—which preserves solutions and reduces total weight—to achieve a PTAS for weighted TSP on H-minor free graphs. This involves partitioning the spanner's edges, guessing which partition contains only epsilon-small-weight edges, contracting that set to create a bounded treewidth graph, solving the TSP optimally on the contracted graph, and then efficiently "opening up" the contracted super-vertices back into the original tour.