Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization
Abstract
Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-k, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.
Related
- Constrained minimization problem and unbounded dynamics for the four-dimensional Klein-Gordon-Schrödinger System
- Nucleation and propagation of brittle fracture as a constrained energy minimization problem
- Budget-Constrained Multi-Consensus Decentralized Gradient Descent
- Well-posedness and discrete-to-continuum convergence of the Kirchhoff Network model
- Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation
BibTeX
@misc{bhoite2026budgetconstrained,
title = {{Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization}},
author = {Omkar Bhoite and V Sateeshkrishna Dhuli and Stefan Werner and Kimmo Kansanen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29790},
eprint = {2609.29790},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29790},
}
RIS
TY - UNPB
TI - Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization
AU - Omkar Bhoite
AU - V Sateeshkrishna Dhuli
AU - Stefan Werner
AU - Kimmo Kansanen
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29790
UR - https://arxiv.org/abs/2609.29790
AB - Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-k, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.
ER -