Local Computation of Maximal Independent Set

2022/10/03 by Ghaffari, Mohsen · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2210.01104

Abstract

We present a randomized Local Computation Algorithm (LCA) with query complexity poly(Δ) ⋅ log n for the Maximal Independent Set (MIS) problem. That is, the algorithm determines whether each node is in the computed MIS or not using poly(Δ) ⋅ log n queries to the adjacency lists of the graph, with high probability, and this can be done for different nodes simultaneously and independently. Here Δ and n denote the maximum degree and the number of nodes. This algorithm resolves a key open problem in the study of local computations and sublinear algorithms (attributed to Rubinfeld).

Cited by

• Sublinear Metric Steiner Forest via Maximal Independent Set
• A Fast Coloring Oracle for Average Case Hypergraphs
• A 0.51-Approximation of Maximum Matching in Sublinear n^1.5 Time
• Lower Bounds for Non-adaptive Local Computation Algorithms

Related

• An Improved Distributed Algorithm for Maximal Independent Set
• Local Computation Algorithms for Graphs of Non-Constant Degrees
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Beyond Worst Case Local Computation Algorithms
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets