More Web Proxy on the site http://driver.im/

research-article

Distributed Approximation on Power Graphs

Authors:

Reuven Bar-Yehuda,

Keren Censor-Hillel,

Sriram V. PemmarajuAuthors Info & Claims

PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

Pages 501 - 510

https://doi.org/10.1145/3382734.3405750

Published: 31 July 2020 Publication History

Abstract

We investigate graph problems in the following setting: we are given a graph G and we are required to solve a problem on G². While we focus mostly on exploring this theme in the distributed CONGEST model, we also show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on G² would be quite difficult to solve efficiently on G, due to congestion. However, we show that the picture is both more complicated and more interesting.

Specifically, we encounter two phenomena acting in opposing directions: (i) slowdown due to congestion and (ii) speedup due to structural properties of G². We demonstrate these two phenomena via two fundamental graph problems, namely, Minimum Vertex Cover (MVC) and Minimum Dominating Set (MDS). Among our many contributions, the highlights are the following.

(1) In the CONGEST model, we show an O(n/∈)-round (1 + ∈)-approximation algorithm for MVC on G², whereas no o(n²)-round algorithm is known for any better-than-2 approximation for MVC on G.

(2) We show a centralized polynomial time 5/3-approximation algorithm for MVC on G², whereas a better-than-2 approximation is UGC-hard for G.

(3) In contrast, for MDS, in the CONGEST model, we show an [EQUATION] lower bound for a constant approximation factor for MDS on G², whereas an Ω(n²) lower bound for MDS on G is known only for exact computation.

References

[1]

Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In Proc. Int. Symp. on Distributed Computing (DISC).

[2]

Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. 2019. Hardness of Distributed Optimization. In Proc. ACM Symp. on Principles of Distributed Computing (PODC).

Digital Library

[3]

Brenda S. Baker. 1994. Approximation Algorithms for NP-Complete Problems on Planar Graphs. J. ACM 41, 1 (1994).

Digital Library

[4]

Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus, Shreyas Pai, and Sriram Pemmaraju. 2020. Distributed Approximation on Power Graphs. CoRR abs/2006.03746 (2020). http://arxiv.org/abs/2006.03746

[5]

Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. 2017. A Distributed (2 + ∈)-Approximation for Vertex Cover in O(log Δ / ∈ log log Δ) Rounds. J. ACM 64, 3 (2017).

Digital Library

[6]

Reuven Bar-Yehuda and Shimon Even. 1983. A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem. In Proceedings of the WG '83, International Workshop on Graph theoretic Concepts in Computer Science.

[7]

Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. 2018. A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log N log Δ/log² log Δ) Rounds. In SIROCCO, 2018.

[8]

Keren Censor-Hillel and Michal Dory. 2018. Distributed Spanner Approximation. In Proc. ACM Symp. on Principles of Distributed Computing (PODC).

Digital Library

[9]

Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. 2018. Distributed construction of purely additive spanners. Distributed Computing 31, 3 (2018).

[10]

Keren Censor-Hillel, Seri Khoury, and Ami Paz. 2017. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In Proc. Int. Symp. on Distributed Computing (DISC).

[11]

Jianer Chen and Iyad Kanj. 2000. On Approximating Minimum Vertex Cover for Graphs with Perfect Matching. In Proceedings of the 11th International Conference on Algorithms and Computation (ISAAC '00). Springer-Verlag, Berlin, Heidelberg.

Digital Library

[12]

Artur Czumaj and Christian Konrad. 2018. Detecting Cliques in CONGEST Networks. In Proc. Int. Symp. on Distributed Computing (DISC).

[13]

Janosch Deurer, Fabian Kuhn, and Yannic Maus. 2019. Deterministic Distributed Dominating Set Approximation in the CONGEST Model. In Proc. ACM Symp. on Principles of Distributed Computing (PODC).

Digital Library

[14]

Michael Elkin. 2004. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In Proc. ACM Symp. on Theory of Computing (STOC).

Digital Library

[15]

Uriel Feige. 1998. A Threshold of Ln n for Approximating Set Cover. J. ACM 45, 4 (July 1998), 634--652.

Digital Library

[16]

Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. 2018. Possibilities and Impossibilities for Distributed Subgraph Detection. In Proc. ACM Symp. on Parallelism in Algorithms and Architecture (SPAA).

Digital Library

[17]

Dimitris Fotakis, Grammati Pantziou, George Pentaris, and Paul Spirakis. 1999. Frequency Assignment in Mobile and Radio Networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1999).

[18]

Pierre Fraigniaud, Amos Korman, and David Peleg. 2013. Towards a complexity theory for local distributed computing. J. ACM 60, 5 (2013).

Digital Library

[19]

Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. 2012. Networks cannot compute their diameter in sublinear time. In Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA).

[20]

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.

Digital Library

[21]

Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. 2018. On Derandomizing Local Distributed Algorithms. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA.

[22]

Mohsen Ghaffari and Fabian Kuhn. 2018. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In Proc. Int. Symp. on Distributed Computing (DISC).

[23]

Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. 2017. On the Complexity of Local Distributed Graph Problems. In Proc. ACM Symp. on Theory of Computing (STOC). ACM.

Digital Library

[24]

Magnús M. Halldórsson. 1995. Approximating Discrete Collections via Local Improvements. In Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA).

[25]

Lujun Jia, Rajmohan Rajaraman, and Torsten Suel. 2002. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing 15, 4 (2002).

[26]

Subhash Khot and Oded Regev. 2008. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74, 3 (2008).

Digital Library

[27]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2016. Local Computation: Lower and Upper Bounds. J. ACM 63, 2 (2016).

Digital Library

[28]

Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, New York, NY, USA.

Digital Library

[29]

Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. 2003. MST construction in O(log log n) communication rounds. In Proc. ACM Symp. on Parallelism in Algorithms and Architecture (SPAA).

Digital Library

[30]

Carsten Lund and Mihalis Yannakakis. 1994. On the Hardness of Approximating Minimization Problems. J. ACM 41, 5 (Sept. 1994), 960--981.

Digital Library

[31]

Noam Nisan. 2002. The Communication Complexity of Approximate Set Packing and Covering. In Automata, Languages and Programming. Springer-Verlag.

[32]

Gopal Pandurangan, David Peleg, and Michele Scquizzato. 2016. Message Lower Bounds via Efficient Network Synchronization. In SIROCCO.

[33]

David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.

Digital Library

[34]

David Peleg and Vitaly Rubinovich. 2000. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM J. Comput. 30, 5 (2000).

Digital Library

[35]

Vaclav Rozhoň and Mohsen Ghaffari. 2020. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In Proc. ACM Symp. on Theory of Computing (STOC).

Digital Library

[36]

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2012. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41, 5 (2012).

[37]

Zhendong Shao, Roger K. Yeh, and David Zhang. 2008. The L(2,1)-labeling on graphs and the frequency assignment problem. Applied Mathematics Letters 21, 1 (2008).

[38]

Vijay V. Vazirani. 2001. Approximation Algorithms. Springer-Verlag.

Digital Library

[39]

David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms (1st ed.). Cambridge University Press, USA.

Digital Library

Cited By

Maus YPeltonen SUitto JOshman RNolin AHalldorsson MBalliu A(2023)Distributed Symmetry Breaking on Power Graphs via SparsificationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594579(157-167)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594579
Akhoondian Amiri SWiederhake B(2022)Distributed distance-r covering problems on sparse high-girth graphsTheoretical Computer Science10.1016/j.tcs.2022.01.001Online publication date: Jan-2022
https://doi.org/10.1016/j.tcs.2022.01.001
Akhoondian Amiri SWiederhake B(2021)Distributed Distance-r Covering Problems on Sparse High-Girth GraphsAlgorithms and Complexity10.1007/978-3-030-75242-2_3(37-60)Online publication date: 4-May-2021
https://doi.org/10.1007/978-3-030-75242-2_3

Distributed Approximation on Power Graphs
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs

We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank $r$. Our main result is a deterministic algorithm to generate a matching which is an $O(r)$-approximation ...
Distributed Minimum Cut Approximation
DISC 2013: Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205

We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round, O log n bits can be transmitted over each edge a.k.a. the CONGEST model. The first ...
Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs

Given an $n$-vertex $m$-edge graph $G$ with nonnegative edge-weights, a shortest cycle is one minimizing the sum of the weights on its edges. The girth of $G$ is the weight of a shortest cycle. We obtain several new approximation algorithms for computing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

July 2020

539 pages

ISBN:9781450375825

DOI:10.1145/3382734

General Chair:
Yuval Emek
Technion, Israel
,
Program Chair:
Christian Cachin
University of Bern, Switzerland

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

European Union

Conference

PODC '20

Sponsor:

PODC '20: ACM Symposium on Principles of Distributed Computing

August 3 - 7, 2020

Virtual Event, Italy

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
109
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Maus YPeltonen SUitto JOshman RNolin AHalldorsson MBalliu A(2023)Distributed Symmetry Breaking on Power Graphs via SparsificationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594579(157-167)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594579
Akhoondian Amiri SWiederhake B(2022)Distributed distance-r covering problems on sparse high-girth graphsTheoretical Computer Science10.1016/j.tcs.2022.01.001Online publication date: Jan-2022
https://doi.org/10.1016/j.tcs.2022.01.001
Akhoondian Amiri SWiederhake B(2021)Distributed Distance-r Covering Problems on Sparse High-Girth GraphsAlgorithms and Complexity10.1007/978-3-030-75242-2_3(37-60)Online publication date: 4-May-2021
https://doi.org/10.1007/978-3-030-75242-2_3

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents