Title: On rounding algorithms for the 2-edge-connected spanning subgraph problem
Data: 11 de julho de 2024 – 5a feira – 9h - https://meet.google.com/cvy-maig-ery
Student: Gabriel Morete de Azevedo

Abstract: A connected loopless graph is 2-edge-connected if it remains connected after the removal of at most one of its edges. Many combinatorial optimization problems seek, for a given graph with costs on its edges, a spanning subgraph satisfying certain connectivity constraints. The minimum 2-edge-connected spanning subgraph problem (2-ECSSP) is a problem of this type. It can be formulated as an integer linear program that selects edges of minimum total cost satisfying the restriction that every cut of the given graph is covered by at least two of the selected edges. This problem is known to be NP-hard. This thesis develops approximation algorithms for three variants of 2-ECSSP, focusing on rounding half-integral solutions of the linear relaxation. This family of solutions often yields the largest known integrality ratio for various subproblems of 2-ECSSP.

The first problem we investigate is the half-integral 2-ECSSP with unrestricted costs. We develop a novel 5/3-approximation that, to the best of our knowledge, is the first one with a factor better than 2. Moreover, we design a reduction scheme, restricting the problem to 4-edge-connected graphs with maximum degree at most five.

Then, we study the matching augmentation problem (MAP), a subproblem of 2-ECSSP in which edge costs are either 0 or 1 and a matching defines the zero cost edges. We survey a better-than-2-approximation, obtained in 2022 by Bamas, Drygala, and Svensson, presenting a comprehensive proof of their result and determining an improved approximation ratio. Additionally, we address conjectures posed in their work and present computational experiments to support our findings.

Finally, we discuss the 2-edge-connected spanning multisubgraph problem (2-ECSMP), a variation of 2-ECSSP in which multiple copies of the same edge can be selected. We survey a recent work by Boyd et al. on a 4/3-approximation for the half-integral 2-ECSMP and leverage their techniques to prove novel decomposition theorems for 4-regular 4-edge-connected graphs. Finally, we pose two conjectures concerning extensions of the decomposition results, suggesting new research directions