PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Omkar Bhoite, V Sateeshkrishna Dhuli, Stefan Werner, Kimmo Kansanen

arXiv:2609.29790v1math.OCcs.SIeess.SP

TL;DR

The paper studies how to augment a fixed weighted network under a budget while choosing both new links and their weights, a setting not covered by prior budgeted augmentation work on such deployed graphs. It combines an SDP relaxation, rounding-and-repair recovery, and an exact-k cost-aware greedy heuristic. Experiments show that distance-dependent costs constrain resistance reduction and shift installed conductance toward shorter links.

  • Problem

    The paper addresses budget-constrained augmentation of a fixed weighted base graph, jointly choosing candidate links and their weights where prior work does not cover this setting.

    Source: §I · p. 1

  • Method

    The approach combines an SDP relaxation and feasible rounding procedures with an exact-k, budget-feasible greedy method using rank-one updates and biharmonic-distance caching.

    Source: §I · p. 2

  • Results

    Under fixed budgets, distance-dependent costs limit attainable total-effective-resistance reduction and shift installed conductance toward shorter links.

    Source: §I · p. 2, §VII · p. 11

  • Takeaways & Limitations

    The SDP relaxation supplies a lower bound for estimating the suboptimality of feasible discrete designs, while distance-dependent costs shape both attainable resistance reduction and installed conductance location.

    Source: §VII · p. 11

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses budgeted augmentation of a fixed weighted graph, a setting not covered by prior work combining link selection and weight allocation under these constraints. It develops an SDP relaxation and feasible recovery procedures alongside a cost-aware greedy method; experiments show distance-dependent costs limit resistance reduction and favor shorter links.

I. INTRODUCTION

  • The Kirchhoff index measures global connectivity through total effective resistance, which accounts for the cumulative contribution of all routes between node pairs.Prior trace formulations involve a Laplacian pseudoinverse that can become a computational bottleneck on large graphs.Source: §I · p. 1
  • The problem jointly selects exactly k candidate edges and assigns their weights under heterogeneous per-unit deployment costs and a total budget on a fixed weighted base graph.The related-work discussion identifies budgeted augmentation of a fixed weighted base graph as distinct from prior formulations, including an SDP that designs from scratch.Source: §I · p. 1
  • The SDP relaxation lower-bounds the mixed-integer optimum, while rounding and repair recover feasible discrete designs for comparison with the numerical benchmark.The paper compares top-k rounding with support-based weight re-optimization and greedy recovery on the SDP support.Source: §I · p. 2
  • The cost-aware greedy method selects edges by marginal resistance reduction, using biharmonic-distance caching and rank-one updates, and is analyzed against a Bellman value-to-go benchmark.The analysis gives a local progress and residual-decay characterization with a conservative spectral lower bound on the local policy ratio.Source: §I · p. 2
  • Distance-dependent costs limit attainable reductions in total effective resistance and shift added-edge weight toward shorter links under fixed budgets.The experimental study covers synthetic and real-world networks, solver behavior, rounding schemes, and added-edge spatial footprints.Source: §I · p. 2

II. PROBLEM FORMULATION AND SDP RELAXATION

The formulation augments a connected, pre-deployed weighted graph by selecting exactly k candidate edges and allocating their weights under a total budget and per-edge bounds. Relaxing binary selections and lifting the trace-inverse objective yields a convex SDP lower bound, with rounding and repair used to recover feasible discrete designs.

II. PROBLEM FORMULATION AND SDP RELAXATION

  • The model keeps existing base-edge weights fixed and jointly chooses candidate-edge weights and binary selections under a total budget, weight bounds, and an exact-k constraint.Candidate-edge weights represent link strength, and per-unit costs may reflect length, terrain, or installation overhead.Source: §II · pp. 2–3
  • The SDP relaxation replaces binary selections with values in [0, 1] and uses a Schur-complement lift to represent the trace-inverse objective without explicit matrix inversion.Direct iterative evaluation can require repeated factorizations or linear solves with worst-case dense arithmetic cost O(n^3).Source: §II · p. 3
  • For a connected base graph, the relaxed optimum lower-bounds the mixed-integer optimum, and the optimal auxiliary matrix equals M^-1(w).The difference between this lower bound and any feasible discrete design's objective upper-bounds that design's absolute suboptimality.Source: §II · p. 3
  • At a relaxed KKT point, every candidate with inactive selection-induced weight bounds has cost-normalized marginal benefit equal to the budget multiplier.If at least one such candidate exists, the multiplier is positive and the budget is active.Source: §II · p. 3
  • Top-k rounding selects the k largest relaxed selection values, breaking ties by lower unit cost, then clips weights to the selected support's bounds and repairs budget use.If the minimum weights on that support already exceed the budget, the procedure obtains no feasible rounded upper bound.Source: §II · pp. 3–4
  • The normalized gap certificate is available only when rounding and repair produce a feasible discrete pair.A support whose minimum required weights exceed the budget yields no feasible upper bound for that budget and cardinality.Source: §II · p. 4

III. CONIC OPTIMIZATION VIA OPERATOR SPLITTING

The SDP is assembled as a standard cone program and solved with an HSDE–ADMM operator-splitting framework. Its sparse formulation has assembly cost O(n^2 + p), while the dominant cone projection requires an eigendecomposition; the normalized embedding residual does not itself certify recovered KKT accuracy.

III. CONIC OPTIMIZATION VIA OPERATOR SPLITTING

  • The conic formulation encodes the block LMI with a vectorized semidefinite slack, represents budget and weight bounds with nonnegative slack blocks, and imposes exact cardinality through a zero-cone block.The candidate-edge Laplacian contributes sparse rank-one coefficients to the LMI.Source: §III · p. 4
  • Conic data assembly costs O(n^2 + p), independent of the chosen cardinality k.The assembled constraint matrix has O(n^2 + p) nonzeros.Source: §III · p. 4
  • HSDE–ADMM applies projections to a homogeneous self-dual embedding; a positive τ with κ = 0 recovers KKT solutions, while τ = 0 with κ > 0 yields infeasibility certificates.The fixed sparse linear system can be factorized once, with later iterations reusing the factors.Source: §III · p. 4
  • The dominant cone projection is an eigendecomposition of the 2n × 2n semidefinite block with worst-case cost O(n^3), while the remaining stated operations cost O(p) and O(n^2 + p).For N4, the dominant HSDE operation is the eigendecomposition of a 2,000 × 2,000 PSD block.Source: §III · pp. 4–5
  • The normalized embedding residual supports stopping but measures embedding feasibility rather than recovered KKT accuracy, so primal, dual, and duality-gap residuals are also reported.Those residuals are reported for instances N1 to N4.Source: §III · p. 5

IV. BUDGETED GREEDY AUGMENTATION VIA RANK-ONE UPDATES

The section develops a budget-feasible greedy method for exact-k graph augmentation and analyzes its progress against a Bellman-optimal value-to-go. Rank-one updates and cached distances make the method scalable, while its guarantees do not amount to a global approximation ratio.

IV. BUDGETED GREEDY AUGMENTATION VIA RANK-ONE UPDATES

  • At each iteration, the heuristic chooses the admissible edge with the largest marginal resistance reduction while reserving enough budget for remaining minimum-weight additions.The reserve rule guarantees exactly k additions whenever the budget and cardinality pair is feasible.Source: §IV · p. 5
  • A reserve-capped trial weight uses an even provisional spend over remaining additions, capped to preserve the minimum-weight reserve.Admissible trial weights remain within [wmin, wmax].Source: §IV · pp. 5–6
  • When k≤p and C≥wmin times the sum of the k cheapest candidate costs, the reserve-capped greedy algorithm returns a feasible exact-k design.The condition is necessary and sufficient for feasibility of the mixed-integer problem.Source: §IV · p. 6
  • Biharmonic-distance caching evaluates candidate gains in constant time, while Sherman–Morrison updates maintain inverse caches in O(n^2) per addition.After one-time setup, the stated total complexity is O(n^3 + k(p + n^2)).Source: §IV · p. 6
  • The analysis does not claim a global approximation ratio; residual-decay bounds alone do not imply a direct global greedy-value guarantee.Such a guarantee requires additional structure linking the greedy successor state to the residual value function.Source: §IV · pp. 6–7
  • The Bellman benchmark defines optimal and greedy cumulative gains from each reachable state, with greedy gain bounded above by the optimal value-to-go.Theorem 5 characterizes residual decay along the realized greedy trajectory using state-dependent local policy ratios.Source: §IV · pp. 6–7
  • Spectral envelopes provide a conservative uniform lower bound on the local policy ratio when the augmented matrices are positive definite.Theorem 7 uses that bound to make the uniform decay envelope computable.Source: §IV · p. 7

V. EXPERIMENTAL SETUP

The experiments compare the SDP relaxation, its rounding, and the greedy algorithm on synthetic and real infrastructure networks. They vary graph size, weight dispersion, candidate-edge costs, and budgets while holding shared inputs fixed for algorithmic comparisons.

V. EXPERIMENTAL SETUP

  • The synthetic study uses four increasingly large instances with average degree 6, while real-network cases include the IEEE 57-bus grid and a 49-airport OpenFlights component.The synthetic setup varies lognormal base-weight dispersion across three settings.Source: §V · pp. 7–8
  • Candidate edges come from clustered k-nearest neighbors, with weights constrained to the upper part of the base-weight spectrum.Nodes are partitioned into three clusters, linked to three in-cluster neighbors, and connected across clusters by backbone edges.Source: §V · p. 8
  • Per-unit deployment cost combines a baseline with a length penalty, swept across β values from 0 to 3.2.At β=0 geometry has no effect; larger β increasingly penalizes long candidate edges.Source: §V · p. 8
  • Five budgets span severe constraints through nearly unrestricted additions, with levels derived from candidate costs and minimum feasible spending.The budget levels are held fixed across the β sweep.Source: §V · p. 8
  • The SDP relaxation, rounding, and greedy algorithm receive the same inputs at each operating point to isolate algorithmic behavior.The n=50 comparison averages normalized total effective resistance over 20 random base graphs, with budgets and β varied.Source: §V · p. 8

VI. RESULTS

Across the real networks, the numerical SDP benchmark is below both feasible methods; distance penalties widen the separation between rounding and greedy. Experiments also show budget saturation in the relaxed problem, rounding gaps concentrated at intermediate cardinalities, and conductance shifting toward shorter links as distance penalties grow.

Solver behavior

  • At the ε = 10^-6 embedding-residual stopping tolerance, εdual and εgap fall below 10^-6 on N1–N4, while εpri remains above it, marginally on N1–N2 and on N3–N4.The tolerance applies to the embedding residual rt; εpri, εdual, and εgap are relative residuals of (P2).Source: §VI · p. 9, Table III · p. 9

Greedy diagnostics

  • In the illustrated greedy stress case, the Bellman-optimal value-to-go is about 1.13 times greedy’s, and the realized next value stays within the contraction ceiling.The example uses n = 14, p = 8, β = 3.2, σ = 0.5, k = 4, and a budget about 1.2 times the minimum spend for four edges at wmin.Source: §VI · p. 9

Algorithm comparison

  • Under strong distance-dependent costs, greedy trails rounding at larger β because exact-k greedy must install all k edges and spreads the budget thinner.The feasible range of k also narrows as β grows and the budget tightens, because each edge must receive at least wmin.Source: §VI · p. 10
  • For n = 50, increasing the budget from C = 58.89 to C = 88.34 lowers the normalized flattening level from about 0.5 to near 0.44; n = 500 shows the same saturation trend.The n = 500 panel reports raw Rtot values on a different budget scale.Source: §VI · p. 10

Real-network case studies

  • Across both real networks and all β, the numerical SDP benchmark lies below both feasible methods; greedy and rounding nearly coincide at β = 0 but separate as β grows.At β = 3.2, rounding is below greedy across intermediate k on the IEEE 57-bus grid, with the same ordering but a smaller gap on OpenFlights.Source: §VI · p. 10

Rounding quality

  • Rounding’s relative gap peaks at an intermediate k, moves to lower k as the budget tightens, and grows with σ before decaying in the saturation regime.The rounded solution is closest to the numerical SDP benchmark at small k and in saturation; the worst penalty is concentrated at intermediate k under heavy-tailed weights.Source: §VI · p. 10
  • Across both regimes, the numerical SDP benchmark lies below every rounding scheme; two-stage dominates top-k, while greedy on SDP support is competitive at small k.Two-stage retains the top-k support but re-optimizes its weights.Source: §VI · p. 11

Spatial footprint

  • As β rises from 0.4 to 3.2 at n = 1000, the SDP concentrates conductance sharply on short edges, while greedy retains a broader tail of longer edges with large marginal resistance reductions.At β = 0.4, the rounding and SDP KDEs nearly coincide; the curves separate further as β grows.Source: §VI · p. 11

VII. CONCLUSION

The paper combines an SDP relaxation, feasible rounding, and cost-aware greedy augmentation for exact-k augmentation of a fixed weighted graph. Its experiments show that distance-dependent costs reshape attainable resistance reduction and installed-conductance geometry, while its greedy analysis provides a local residual-decay interpretation and a conservative policy-ratio floor.

VII. CONCLUSION

  • Distance-dependent per-unit costs reshape both attainable resistance reduction and the spatial layout of installed conductance, distinguishing cost-aware augmentation from uniform-cost installation.The conclusion also notes that re-optimizing weights on a rounded support recovers much of the performance lost by naive top-k rounding and repair.Source: §VII · p. 11
  • The SDP relaxation lower-bounds the mixed-integer optimum, providing an a posteriori gap estimate for feasible discrete designs.The estimate is relative to the numerical SDP benchmark.Source: §VII · p. 11
  • The Bellman analysis gives the greedy method a local residual-decay interpretation and a conservative spectral floor on its local policy ratio.Source: §VII · p. 11

APPENDIX A

Appendix A uses Bellman recursion and backward induction to relate greedy accumulated gains to the value-to-go benchmark. It then derives residual-decay bounds, including an exponential form.

APPENDIX A

  • Backward induction establishes that the greedy value-to-go estimate is bounded above by the Bellman-optimal value-to-go.The proof sets both values to zero when no feasible edges or remaining augmentations exist, then uses the induction hypothesis and Bellman optimality.Source: Appendix A · p. 11
  • The greedy value is nonnegative and no greater than the value-to-go benchmark, using nonnegative one-step gains and the established value bound.Source: Appendix A · p. 11
  • Multiplying stepwise contraction factors yields residual-decay bounds, and 1 − z ≤ e^−z converts the product into an exponential estimate.The subsequent bound substitutes the remaining augmentation count, lower-bounds each local policy ratio by ρ_min, and uses a harmonic sum in the exponent.Source: Appendix A · pp. 11–12

APPENDIX B

Appendix B bounds greedy one-step gains and the value-to-go over reachable states. The argument relies on positive-semidefinite rank-one updates, bounded selected weights, and spectral bounds on the shifted Laplacian.

APPENDIX B

  • Positive-semidefinite rank-one updates, no repeated candidate edges, and weights in [w_min, w_max] constrain every realized greedy iterate.Source: Appendix B · p. 12
  • Rayleigh-quotient bounds on the shifted-Laplacian spectrum bound feasible edges’ resistance and squared-biharmonic-distance terms, yielding lower and upper one-step-gain bounds.The lower bound uses w_min in the numerator and w_max in the denominator; the upper bound uses the spectral lower bound.Source: §IV · p. 6, Appendix B · p. 12
  • Bounding each remaining one-step gain by δ_max and counting at most k_rem remaining augmentations bounds the value-to-go by k_rem δ_max.Source: Appendix B · p. 12
Loading 2609.29790v1…