On the chance-constrained minimum spanning $k$-core problem

Abstract

A graph is called a $k$-core if every vertex has at least $k$ neighbors. If the parameter $k$ is sufficiently large relative to the number of vertices, a $k$-core is guaranteed to possess 2-hop reachability between all pairs of vertices. Furthermore, it is guaranteed to preserve those pairwise distances under arbitrary single-vertex deletion. Hence, the concept of a $k$-core can be used to produce 2-hop survivable network designs, specifically to design inter-hub networks. Formally, given an edge-weighted graph, the minimum spanning $k$-core problem seeks a spanning subgraph of the given graph that is a $k$-core with minimum total edge weight. For any fixed $k$, this problem is equivalent to a generalized graph matching problem and can be solved in polynomial time. This article focuses on a chance-constrained version of the minimum spanning $k$-core problem under probabilistic edge failures. We first show that this probabilistic version is NP-hard, and we conduct a polyhedral study to strengthen the formulation. The quality of bounds produced by the strengthened formulation is demonstrated through a computational study.