Ear-Decompositions, Matchings, and Matroids
Vera Traub, Jens Vygen · Cambridge University Press eBooks · 2024
By combining the removable pairing technique presented in Chapter 12 with a new approach based on ear-decompositions and matroid intersection, Sebő and Vygen improved the approximation ratio for Graph TSP from 13/9 to 7/5. We will present this algorithm, which is still the best-known approximation algorithm for Graph TSP, in this chapter. An interesting feature of this algorithm is that it is purely combinatorial, does not need to solve a linear program, and runs in O( n 3 ) time. To describe the algorithm, we review some matching theory, including a theorem of Frank that links ear-decompositions to T -joins. A slight variant of the Graph TSP algorithm is a 4/3-approximation algorithm for finding a smallest 2-edge-connected spanning subgraph, which was the best known for many years. The proofs will also imply corresponding upper bounds on the integrality ratios.