Simple and local independent set approximation

DOI10.1016/J.TCS.2020.09.018MaRDI QIDQ5919021zbMATH OpenOpenAlexFDO

Authors Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz

Publication date 6 November 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.00786

zbMATH Keywords

approximation algorithmdistributed algorithmindependent setTurán bound

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Abstract: We bound the performance guarantees that follow from Tur'an-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight $(Delta+1)/2$-approximation in unweighted graphs of maximum degree $Delta$, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a $Delta$-approximation, but a simple modification results in an asymptotic expected $0.529Delta$-approximation. This compares with a recent, more complex $Delta$-approximation~cite{BCGS17}, which holds deterministically.

Recommendations

• Simple and local independent set approximation
• Brief announcement: Simple and local independent set approximation
• scientific article; zbMATH DE number 1003268
• Improved approximations of independent sets in bounded-degree graphs
• Distributed large independent sets in one round on bounded-independence graphs

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A note on greedy algorithms for the maximum weighted independent set problem
• A probabilistic lower bound on the independence number of graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• An optimal bit complexity randomized distributed MIS algorithm
• Approximation Resistance from Pairwise-Independent Subgroups
• Brief Announcement
• Computing large independent sets in a single round
• Distributed approximation of maximum independent set and maximum matching
• Distributed Computing: A Locality-Sensitive Approach
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Hardness of Distributed Optimization
• scientific article; zbMATH DE number 3365308 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Local computation: lower and upper bounds
• Lower bounds on the independence number in terms of the degrees
• On approximation properties of the independent set problem for low degree graphs
• On constant time approximation of parameters of bounded degree graphs
• On the complexity of local distributed graph problems
• On the Lovász theta function for independent sets in sparse graphs
• Online set packing
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Small transversals in hypergraphs
• Streaming algorithms for independent sets in sparse hypergraphs
• The probabilistic method

Cited in

(8)

• Distributed large independent sets in one round on bounded-independence graphs
• Approximating weighted neighborhood independent sets
• Local interactions and \(p\)-best response set
• Brief announcement: Simple and local independent set approximation
• Brief Announcement
• Simple and local independent set approximation
• Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
• Distributed fractional local ratio and independent set approximation

This page was built for publication: Simple and local independent set approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919021)