Locally computing edge orientations

We consider the question of orienting the edges in a graph 𝐺 such that every vertex has bounded out-degree. For graphs of arboricity 𝛼, there is an orientation in which every vertex has out-degree at most 𝛼, and moreover, this is the best possible. We are thus interested in algorithms that can achieve a maximum out-degree of close to 𝛼. 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 (𝑢, 𝑣)?” 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 Ω(𝑛) probes per query on an 𝑛-vertex graph. In the case where 𝐺 has unbounded degree, we show that any LCA which orients its edges to yield maximum out-degree 𝑟 must use Ω( √ 𝑛/𝑟) probes to 𝐺 per query in the worst case, even if 𝐺 is known to be a forest (that is, 𝛼 = 1). We also show several algorithms with sublinear probe complexity when 𝐺 has unbounded degree. When the maximum degree Δ of 𝐺 is bounded, we demonstrate an algorithm that uses [formulation] probes to 𝐺 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 result to demonstrate an LCA which can 4-color any tree using sublinear probes per query.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Singhal, Mihir

Advisor dc:contributor.advisor

• Rubinfeld, Ronitt

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/151520

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/151520