Approximation Algorithms for Survivable Network Design Problems

You are cordially invited to attend the PhD Dissertation Defence of Miguel Bosch Calvo on Tuesday 20 January 2026 at 10:00 in room D0.02.

Abstract:
Connectivity is among the most extensively studied branches of graph theory. It is closely related to the design of networks, which has many practical applications. An straight-forward application of connectivity is the design of networks that can withstand failures or attacks, i.e., networks that stay connected even after some of its elements are removed. This type of problems fall into the category of survivable network design problems. Most survivable network design problems are NP-hard, so no efficient algorithm is known to optimise them. In light of this, efficient heuristics are often designed for these problems. The design and rigorous analysis of heuristics is denoted in the theoretical computer science community as approximation algorithms. In this thesis we study approximation algorithms for connectivity problems. In particular, we focus on the $2$-edge-connected spanning subgraph problem and the $2$-vertex-connected spanning subgraph problem. We say that a graph $G$ is $2$-edge-connected (resp., $2$-vertex-connected) if it is connected and the removal of one edge (resp., one vertex) does not disconnect the graph. In the $2$-edge-connected spanning subgraph problem (resp., $2$-vertex-connected spanning subgraph problem) we are given a graph $G=(V, E)$ and we want to find a minimum cardinality subset $S\subseteq E$ such that $(V, S)$ is $2$-edge-connected (resp., $2$-vertex-connected). The main contribution of this thesis is that we improve upon the state of the art of the aforementioned problems, in terms of approximation algorithms. To do so we use techniques based on generalizations of the well-known maximum matching problem, and study problems related to matchings that are interesting on their own. We also present in this thesis results in that area.

Dissertation Committee:
- Prof. Fabrizio Grandoni, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Andrea Emilio Rizzoli, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Laura Sanità, Bocconi University, Italy (External Member)
- Prof. Jens Vygen, University of Bonn, Germany (External Member)