Solving chance-constrained spanning $k$-core problem via decomposition and integer programming

Abstract

Given a non-negative integer $k$, a graph of minimum degree at least $k$ is called a $k$-core. The concept of $k$-cores can be used to design resilient networks that preserve low diameter and high vertex-connectivity upon limited vertex or edge failures. This article focuses on a chance-constrained version of the minimum spanning $k$-core problem under probabilistic edge failures. Specifically, given that the edges can fail randomly and independently, we want to find a subset of edges of minimum total cost such that the graph with this edge set is a $k$-core with probability at least $1-\alpha$ where $\alpha \in [0,1]$. We first reformulate the non-convex chance-constrained optimization problem as a large-scale integer program. To solve it, we employ a decomposition and branch-and-cut framework recently introduced in the literature and discuss problem-specific enhancements of this approach. We report on our computational experiments designed to benchmark this decomposition branch-and-cut algorithm.