DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.154

An LCA for Approximated MST in General Bounded-Degree Graphs

Authors: Reut Levi, Moti Medina, and Daniel Prigan

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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 Õ(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 Õ(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 Õ(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.

Cite as

Reut Levi, Moti Medina, and Daniel Prigan. An LCA for Approximated MST in General Bounded-Degree Graphs. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 154:1-154:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{levi_et_al:LIPIcs.ESA.2026.154,
  author =	{Levi, Reut and Medina, Moti and Prigan, Daniel},
  title =	{{An LCA for Approximated MST in General Bounded-Degree Graphs}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{154:1--154:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.154},
  URN =		{urn:nbn:de:0030-drops-272902},
  doi =		{10.4230/LIPIcs.ESA.2026.154},
  annote =	{Keywords: Locally Computable Algorithms, Sublinear Algorithms, Minimum Spanning Trees, Partition Oracles}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.33

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

Authors: Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We show how to preprocess a weighted undirected n-vertex planar graph in Õ(n^{4/3}) time, such that the distance between any pair of vertices can then be reported in Õ(1) time. This improves the previous Õ(n^{3/2}) preprocessing time [JACM'23]. Our main technical contribution is a near optimal construction of additively weighted Voronoi diagrams in undirected planar graphs. Namely, given a planar graph G and a face f, we show that one can preprocess G in Õ(n) time such that given any weight assignment to the vertices of f one can construct the additively weighted Voronoi diagram of f in near optimal Õ(|f|) time. This improves the Õ(√{n|f|}) construction time of [JACM'23].

Cite as

Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann. Faster Construction of a Planar Distance Oracle with Õ(1) Query Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:LIPIcs.ICALP.2025.33,
  author =	{Boneh, Itai and Golan, Shay and Mozes, Shay and Prigan, Daniel and Weimann, Oren},
  title =	{{Faster Construction of a Planar Distance Oracle with \~{O}(1) Query Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.33},
  URN =		{urn:nbn:de:0030-drops-234106},
  doi =		{10.4230/LIPIcs.ICALP.2025.33},
  annote =	{Keywords: Distance Oracle, Planar Graph, Construction Time}
}

Search Results

Documents authored by Prigan, Daniel

An LCA for Approximated MST in General Bounded-Degree Graphs

Abstract

Cite as

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

Abstract

Cite as

Thanks for your feedback!

Could not send message