Skip to content

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization

Sep 2026 · arXiv.org · Vol abs/2609.29790 · 0 citations · 37 references
Computer Science Mathematics Engineering

TL;DR

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.

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.

View source

Similar papers

Preprint Oct 2026

Constrained modularity maximization in complex networks via branch-and-price

Modularity maximization is widely used to identify community structure in complex networks. In many applications, however, community detection must also incorporate prior knowledge and domain-specific requirements beyond network topology. We study constrained modularity maximization with restrictions on the number of c...

Jaewoo Kim, Seung-yeon Lee, Jaemyung Ahn et al. · 0 citations
Preprint Nov 2026

Approximation Algorithms for Multi-Criteria Network Design Problems

It is shown that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems: Min-max multi-criteria optimization and multi-criteria connectivity augmentation.

Mehrshad Taziki, A. Vakilian · 0 citations
Open access Sep 2026

The h-Hop Dominating Subnetwork Problem: Variants, Structural Properties, and Exact Solution Approaches

This paper introduces the h-hop dominating subnetwork problem (HSDP), a graph-optimization problem that jointly selects a prescribed number of operational vertices, determines the dominant vertices within the selected set, and assigns each selected vertex to a dominant within a given hop range. Unlike classical dominat...

Pablo Adasme, Gustavo Alcántara · 0 citations
Preprint Sep 2026

A $59/33$ Cut-LP Guarantee for Matching Augmentation

A new structural analysis of the Bamas--Drygala--Svensson LP-guided DFS algorithm is given, which combines an exact primal--dual identity for the residual uplink problem with a rank bound that measures fractional support relative to the unit-valued skeleton.

Morteza Alimi, Tobias Mömke · 0 citations
#artificial intelligence Preprint Sep 2026

Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow

This work proposes a scalable continuous-optimization algorithm for large-scale single-commodity FCNFP based on an iteratively reweighted least-squares (IRLS) framework and develops an algorithmic variant that incorporates objective-driven perturbation restarts and an anchor-union restricted search that jointly leverag...

Sindura Saraswathi, C. Kümmerle · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.