Statistics and Computational Methods Seminar Series - Fall 2025

Speaker: Fabio Furini (Sapienza Università di Roma)

Title: Hidden Bilevel Structures in Graph Disconnection Problems: Models and Exact Algorithms

Abstract:

I will begin with a gentle introduction to bilevel optimization problems, highlighting their main applications and the exact methods commonly used to solve them. These foundations will serve as a basis to better understand how bilevel structures naturally arise in complex combinatorial settings. In the central part of the talk, I will then show how these concepts emerge in graph disconnection problems, and how uncovering their hidden bilevel structure leads to stronger formulations and more efficient algorithms. Many fundamental graph disconnection problems hide an underlying bilevel structure that can be exploited for stronger formulations and algorithms. In this talk, we reveal and formalize this hidden structure for two key problems: the capacitated vertex separator and the k-vertex cut. Both are modeled as two-phase bilevel optimization problems, where a leader strategically deletes vertices and a follower reacts by optimizing over the disconnected graph. We present new integer programming formulations naturally capturing this bilevel interaction, supported by families of strengthening valid inequalities and polynomial-time separation procedures. Our computational studies demonstrate that these approaches significantly improve the state of the art, yielding better solutions and faster convergence on benchmark instances. Beyond these two problems, the bilevel perspective opens promising directions for a broader class of graph modification and partitioning problems.

Related resources: 

https://link.springer.com/article/10.1007/s12532-019-00167-1

https://pubsonline.informs.org/doi/10.1287/opre.2021.2110