Brief Announcement: Simple and Local Independent Set Approximation
Pages 163 - 165
Abstract
We bound the performance guarantees that follow from Turán-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 (Δ+1)/2-approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Δ+1)-approximation, but a simple modification results in an asymptotic expected 0.529(Δ+1)-approximation.
References
[1]
Noga Alon . 2010. On Constant Time Approximation of Parameters of Bounded Degree Graphs Property Testing - Current Research and Surveys. 234--239.
[2]
Noga Alon, László Babai, and Alon Itai . 1986. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms Vol. 7, 4 (1986), 567--583.
[3]
Noga Alon and Joel H Spencer . 2016. The probabilistic method (bibinfoeditionfourth ed.). John Wiley & Sons.
[4]
Per Austrin, Subhash Khot, and Muli Safra . 2009. Inapproximability of vertex cover and independent set in bounded degree graphs 24th IEEE CCC. 74--80.
[5]
Nikhil Bansal, Anupam Gupta, and Guru Guruganesh . 2015. On the Lovász Theta function for Independent Sets in Sparse Graphs 47th ACM STOC. 193--200.
[6]
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman . 2017. Distributed Approximation of Maximum Independent Set and Maximum Matching 36th ACM PODC. 165--174.
[7]
Piotr Berman and Toshihiro Fujito . 1999. On Approximation Properties of the Independent Set Problem for Low Degree Graphs. Theory Comput. Syst. Vol. 32, 2 (1999), 115--132.
[8]
Marijke H.L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, and Fabian Kuhn . 2016. Brief Announcement: Local Independent Set Approximation 35th ACM PODC. 377--378.
[9]
Ravi B. Boppana . 1987. Personal communication to Joel Spencer.
[10]
Y. Caro . 1979. New results on the independence number. Technical Report. Tel Aviv Univ.
[11]
Keren Censor-Hillel, Seri Khoury, and Ami Paz . 2017. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model 31st DISC. 10:1--10:16.
[12]
Siu On Chan . 2016. Approximation resistance from pairwise-independent subgroups. J. ACM Vol. 63, 3 (2016), 27.
[13]
Graham Cormode, Jacques Dark, and Christian Konrad . 2017. Independent Set Size Approximation in Graph Streams. Technical Report arXiv:1702.08299. CoRR.
[14]
Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, and Dror Rawitz . 2012. Online set packing. SIAM Journal of Computing Vol. 41, 4 (2012), 728--746.
[15]
Paul ErdH os . 1970. On the graph theorem of Turán (in Hungarian). Mat. Lapok Vol. 21 (1970), 249--251.
[16]
Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus . 2017. On the complexity of local distributed graph problems 49th ACM STOC. 784--797.
[17]
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, and Mario Szegedy . 2016. Streaming Algorithms for Independent Sets in Sparse Hypergraphs. Algorithmica Vol. 76 (2016), 490--501. Issue 2.
[18]
Magnús M. Halldórsson and Christian Konrad . 2018. Computing Large Independent Sets in a Single Round. Distributed Computing Vol. 31, 1 (2018), 69--82.
[19]
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer . 2016. Local Computation: Lower and Upper Bounds. J. ACM Vol. 63, 2, Article bibinfoarticleno17 (2016), bibinfonumpages44 pages.
[20]
P. Turán . 1941. On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok Vol. 48 (1941), 436--452.
[21]
V.K. Wei . 1981. A lower bound on the stability number of a simple graph. Technical Report. Bell Laboratories.
Index Terms
- Brief Announcement: Simple and Local Independent Set Approximation
Recommendations
Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed ComputingOver the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially ...
Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed ComputingWe study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-...
Brief announcement: local approximability of minimum dominating set on planar graphs
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computingWe show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a (7-ε)-approximation of a minimum dominating set on planar graphs, for any positive constant ε. In prior work, the best lower bound on the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2018 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 July 2018
Check for updates
Author Tags
Qualifiers
- Announcement
Funding Sources
- Israel Science Foundation
- Icelandic Research Fund
Conference
PODC '18
PODC '18: ACM Symposium on Principles of Distributed Computing
July 23 - 27, 2018
Egham, United Kingdom
Acceptance Rates
PODC '18 Paper Acceptance Rate 41 of 163 submissions, 25%;
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 96Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in