Locally computing edge orientations

We consider the question of orienting the edges in a graph $G$ such that every vertex has bounded out-degree. For graphs of arboricity $\alpha$, there is an orientation in which every vertex has out-degree at most $\alpha$ and, moreover, the best possible maximum out-degree of an orientation is at least $\alpha -1$. We are thus interested in algorithms that can achieve a maximum out-degree of close to $\alpha$. A widely studied approach for this problem in the distributed algorithms setting is a peeling algorithm'' that provides an orientation with maximum out-degree $α(2+ε)$ in a logarithmic number of iterations. We consider this problem in the local computation algorithm (LCA) model, which quickly answers queries of the form What is the orientation of edge $(u,v)$?‘’ by probing the input graph. When the peeling algorithm is executed in the LCA setting by applying standard techniques, e.g., the Parnas-Ron paradigm, it requires $\mathrm{\Omega }(n)$ probes per query on an $n$-vertex graph. In the case where $G$ has unbounded degree, we show that any LCA that orients its edges to yield maximum out-degree $r$ must use $\mathrm{\Omega }(\sqrt{n}\mathrm{/}r)$ probes to $G$ per query in the worst case, even if $G$ is known to be a forest (that is, $\alpha =1$). We also show several algorithms with sublinear probe complexity when $G$ has unbounded degree. When $G$ is a tree such that the maximum degree $\mathrm{\Delta }$ of $G$ is bounded, we demonstrate an algorithm that uses $\mathrm{\Delta }{n}^{1-{\log }_{\mathrm{\Delta }}r+o(1)}$ probes to $G$ per query. To obtain this result, we develop an edge-coloring approach that ultimately yields a graph-shattering-like result. We also use this shattering-like approach to demonstrate an LCA which $4$-colors any tree using sublinear probes per query.