2026-07-23T03:27:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21053 2024-09-16T06:02:39Z ddc:004 open_access

Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs Levi, Reut Medina, Moti Tubul, Omer Locally Computable Algorithms Sublinear algorithms Spanning Subgraphs Clusterbale Graphs In this paper, we study the problem of locally constructing a sparse spanning subgraph (LSSG), introduced by Levi, Ron, and Rubinfeld (ALGO'20). In this problem, the goal is to locally decide for each e ∈ E if it is in G' where G' is a connected subgraph of G (determined only by G and the randomness of the algorithm). We provide an LSSG that receives as a parameter a lower bound, ϕ, on the conductance of G whose query complexity is Õ(√n/ϕ²). This is almost optimal when ϕ is a constant since Ω(√n) queries are necessary even when G is an expander. Furthermore, this improves the state of the art of Õ(n^{2/3}) queries for ϕ = Ω(1/n^{1/12}). We then extend our result for (k, ϕ_in, ϕ_out)-clusterable graphs and provide an algorithm whose query complexity is Õ(√n + ϕ_out n) for constant k and ϕ_in. This bound is almost optimal when ϕ_out = O(1/√n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Reut Levi and Moti Medina and Omer Tubul 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.60 urn:nbn:de:0030-drops-210537 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.60 eng https://creativecommons.org/licenses/by/4.0/legalcode