2026-09-10T09:44:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27792 2026-09-09T12:19:39Z ddc:004 open_access

Improved Local Computation of Edge Orientation Levi, Reut Rushkin, Bar Local Algorithms Sublinear-time Algorithms Edge Orientation Bounded Arboricity In this paper, we study the problem of orienting the edges of a graph G so that every vertex has bounded out-degree in the local computation algorithms (LCA) model, as defined by Rubinfeld et al. (ICS 2011). More specifically, given a query e ∈ E our algorithm returns the orientation of e such that with high constant probability (namely, at least 0.9) the out-degree of each vertex is bounded by r where r is a parameter. We provide such an upper bound for any r = Ω(arb(G)⋅log n) where arb(G) denotes the arboricity of G (we note that such orientation exists only when r = Ω(arb(G))). Our query complexity is Õ(n⋅arb(G)/r²) in the worst case and O(1) on expectation (over the vertices and the randomness of the algorithm). This generalizes the upper bound by Mitrović-Rubinfeld-Singhal (ESA 2024) that provided a similar upper bound only when r = Ω((arb(G)²⋅n))^{1/3}. For r = Ω(arb(G)⋅log n), our algorithm also improves their weaker upper bound of Õ(n/r) queries for the special case where the input graph is a tree (whose arboricity is 1). Our algorithm assigns each vertex a level derived from locally sampled neighborhoods combined through a staggered multi-scale recursion, inspired by the recent arboricity-approximation framework of Dai–Ghaffari–Portmann (FOCS 2025). The main novelty of our approach is that it reconstructs levels consistently across the graph while simultaneously respecting the out-degree bound and maintaining locality of computation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Reut Levi and Bar Rushkin 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.75 urn:nbn:de:0030-drops-277929 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.75 eng https://creativecommons.org/licenses/by/4.0/legalcode