Fabian Kuhn
ABSTRACT
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Ω(nc/k2/k) and Ω(Δ>1/k/k) for some constant c, where n and Δ denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Ω(√log n/log log n) and Ω(logΔ/ log log Δ). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.
- Y. Afek, S. Kutten, and M. Yung. The Local Detection Paradigm and its Applications to Self-Stabilization. Theoretical Computer Science, 186(1-2):199--229, 1997. Google Scholar
Digital Library
- R. Cole and U. Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Information and Control, 70(1):32--53, 1986. Google ScholarDigital Library
- M. Elkin. A Faster Distributed Protocol for Constructing a Minimum Spanning Tree. In Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 359--368, 2004. Google ScholarDigital Library
- M. Elkin. Unconditional Lower Bounds on the Time-Approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem. In Proc. of the 36th ACM Symposium on Theory of Computing (STOC), 2004. Google ScholarDigital Library
- U. Feige. A Threshold of ln n for Approximating Set Cover. Journal of the ACM (JACM), 45(4):634--652, 1998. Google ScholarDigital Library
- F. Fich and E. Ruppert. Hundreds of impossibility results for distributed computing. Distrib. Comput., 16(2-3):121--163, 2003. Google ScholarDigital Library
- M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of Distributed Consensus With One Faulty Process. J. ACM, 32(2):374--382, 1985. Google ScholarDigital Library
- A. Israeli and A. Itai. A Fast and Simple Randomized Parallel Algorithm for Maximal Matching. Information Processing Letters, 22:77--80, 1986. Google ScholarDigital Library
- F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proc. of the 22nd Annual ACM Symp. on Principles of Distributed Computing (PODC), pages 25--32, 2003. Google ScholarDigital Library
- F. Kuhn and R. Wattenhofer. Distributed Combinatorial Optimization. Technical Report 426, ETH Zurich, Dept. of Computer Science, 2003.Google Scholar
- E. Kushilevitz and Y. Mansour. An Ω(Dlog(N/D)) Lower Bound for Broadcast in Radio Networks. SIAM Journal on Computing, 27(3):702--712, June 1998. Google ScholarDigital Library
- L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst., 4(3):382--401, 1982. Google ScholarDigital Library
- F. Lazebnik and V. A. Ustimenko. Explicit Construction of Graphs with an Arbitrary Large Girth and of Large Size. Discrete Applied Mathematics, 60(1-3):275--284, 1995. Google ScholarDigital Library
- F. Lazebnik, V. A. Ustimenko, and A. J. Woldar. A New Series of Dense Graphs of High Girth. Bulletin of the American Mathematical Society (N.S.), 32(1):73--79, 1995.Google Scholar
- N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193--201, 1992. Google ScholarDigital Library
- Z. Lotker, B. Patt-Shamir, and D. Peleg. Distributed MST for Constant Diameter Graphs. In Proc. of the 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 63--71, 2001. Google ScholarDigital Library
- M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15:1036--1053, 1986. Google ScholarDigital Library
- M. Naor and L. Stockmeyer. What Can Be Computed Locally? In Proc. of the 25th Annual ACM Symp. on Theory of Computing (STOC), pages 184--193, 1993. Google ScholarDigital Library
- D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google ScholarDigital Library
- D. Peleg and V. Rubinovich. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM Journal on Computing, 30(5):1427--1442, 2000. Google ScholarDigital Library
Index Terms
- What cannot be computed locally!
Recommendations
Node and Edge Averaged Complexities of Local Graph Problems
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed ComputingWe continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph G=(V,E) is the average over the times at which the ...
Distributed Lower Bounds for Ruling Sets
Given a graph $G=(V,E)$, an $(\alpha,\beta)$-ruling set is a subset $S\subseteq V$ such that the distance between any two vertices in $S$ is at least $\alpha$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $\beta$. We ...
Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed ComputingWe consider graph coloring and related problems in the distributed message-passing model. \em Locally-iterative algorithms are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a ...
Comments