2026-08-25T15:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27290 2026-08-25T13:18:21Z ddc:004 open_access

An LCA for Approximated MST in General Bounded-Degree Graphs Levi, Reut Medina, Moti Prigan, Daniel Locally Computable Algorithms Sublinear Algorithms Minimum Spanning Trees Partition Oracles We present a local computation algorithm (LCA) for constructing a connected spanning subgraph whose total weight is at most a (1+ε)-factor larger than that of a minimum spanning tree, in general bounded-degree graphs. Prior to our work, nontrivial LCAs for this problem, namely, algorithms with sublinear query complexity, were known only for the restricted graph family of minor-free graphs by Levi, Ron, and Rubinfeld (Algorithmica 2020). The query complexity of our algorithm in terms of the number of vertices, n, is Õ(n^{2/3}). The best known lower bound for this problem is Ω(n^{1/2}). Our approach consists of three conceptual layers. The first is a localized variant of Prim’s algorithm, which reconstructs, using only local queries, a large fraction of the edges of the minimum spanning tree. The resulting subgraph at this stage is disconnected. To address this, in the second layer, we partition the partially constructed forest into clusters of size Õ(n^{1/3}). To this end, we present a partition oracle, as introduced by Hassidim et al. (FOCS 2009), for trees whose query complexity is nearly optimal in terms of ε, the parameter that controls the number of edges in the boundary. In particular, its query complexity is Õ(d/ε), where d denotes the degree bound. In the third and last layer, we adapt the technique from Lenzen-Levi (ICALP 2018) for locally computing a sparse spanning subgraph and obtain an algorithm that locally identifies and adds a small number of carefully chosen edges in order to restore global connectivity. We show that the number of such additional edges is small, and consequently, their total weight contributes only a small amount to the overall cost, preserving the (1+ε)-approximation guarantee. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Reut Levi and Moti Medina and Daniel Prigan 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.154 urn:nbn:de:0030-drops-272902 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.154 eng https://creativecommons.org/licenses/by/4.0/legalcode