Spectral Sparsification Under Locally Bounded Faults

This paper constructs fixed-weight spectral sparsifiers of simple unweighted graphs that remain valid simultaneously under locally bounded vertex and edge failures. The support bound is O(min{m, n log^3(2n)[f/epsilon + epsilon^(-2) log(n/delta)]}), where each surviving vertex loses at most f incident edges. A complete-graph lower bound matches the polynomial dependence on the fault budget and accuracy up to logarithmic factors. The construction is polynomial-time, uses a bounded number of random bits, and outputs rational weights. The paper includes complete proofs, precise model assumptions, prior-work comparisons, limitations, and an AI-methodology disclosure. The record contains the manuscript PDF and reproducible LaTeX source.