Local Algorithms for Sparsification of Average-case Graphs

Given an input graph 𝐺, a Local Computation Algorithm for sparse spanning graphs provides query access to a sparse subgraph 𝐺′ ⊆ 𝐺, where 𝐺′ maintains the connectivity and/or distances in 𝐺, by making a sublinear number of probes to the input 𝐺 for each query to 𝐺′ . It is known that worst-case graphs require Ω(√ 𝑛) probes in order to detect whether a specific edge 𝑒 ∈ 𝐺′ . We want to show that, in expectation, this task can be accomplished much faster, by considering average-case graphs such as Erdos-Renyi random graphs and the Preferential Attachment model. We first present an LCA algorithm which, on an Erdos-Renyi graph input 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛) 𝑛 ), gives fast access to a sparsification 𝐺′ of 𝐺, such that 𝐺′ is connected and has 𝑛+𝑜(𝑛) edges. Queries to 𝐺′ are answered 𝒪(∆ log2 (𝑛)) probes to 𝐺 (where ∆ = 𝒪(𝑝𝑛) is the maximum degree). We then show an LCA algorithm that, for an Erdos-Renyi graph 𝐺 with edge parameter 𝑝 ≥ Ω(log(𝑛)/√ 𝑛 ), gives access to a 4-spanner 𝐺′ of 𝐺 in 𝒪(log2/(𝑛)) probes in expectation per query, such that 𝐺′ has at most 2𝑛 edges. Finally, we give an LCA that runs on a Preferential Attachment graph 𝐺 with edge parameter Θ(log(𝑛)), which gives fast access to a sparsification 𝐺′ of 𝐺 where 𝐺′ is connected and has 𝑛 + 𝑜(𝑛) edges. Each query to 𝐺′ takes an expected 𝒪(log3 (𝑛)) probes to 𝐺.

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

2022

Author dc:creator

• Cao, Ruidi

Advisor dc:contributor.advisor

• Rubinfeld, Ronitt

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

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

Handle dc:identifier.uri

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

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/144952