{"ID":2852618,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.17262","arxiv_id":"2510.17262","title":"Finding 4-Additive Spanners: Faster, Stronger, and Simpler","abstract":"Additive spanners are fundamental graph structures with wide applications in network design, graph sparsification, and distance approximation. In particular, a $4$-additive spanner is a subgraph that preserves all pairwise distances up to an additive error of $4$. In this paper, we present a new deterministic algorithm for constructing $4$-additive spanners that matches the best known edge bound of $\\tilde{O}(n^{7/5})$ (up to polylogarithmic factors), while improving the running time to $\\tilde{O}(\\min\\{mn^{3/5}, n^{11/5}\\})$, compared to the previous $\\tilde{O}(mn^{3/5})$ randomized construction. Our algorithm is not only faster in the dense regime but also fully deterministic, conceptually simpler, and easier to implement and analyze.","short_abstract":"Additive spanners are fundamental graph structures with wide applications in network design, graph sparsification, and distance approximation. In particular, a $4$-additive spanner is a subgraph that preserves all pairwise distances up to an additive error of $4$. In this paper, we present a new deterministic algorithm...","url_abs":"https://arxiv.org/abs/2510.17262","url_pdf":"https://arxiv.org/pdf/2510.17262v1","authors":"[\"Chuhan Qi\"]","published":"2025-10-20T07:48:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}