Document Open Access Logo

Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs

Author Shay Solomon

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.52.pdf
  • Filesize: 0.52 MB
  • 19 pages

Document Identifiers

Author Details

Shay Solomon

Cite AsGet BibTex

Shay Solomon. Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.52

Abstract

In graph sparsification, the goal has almost always been of global nature: compress a graph into a smaller subgraph (sparsifier) that maintains certain features of the original graph. Algorithms can then run on the sparsifier, which in many cases leads to improvements in the overall runtime and memory. This paper studies sparsifiers that have bounded (maximum) degree, and are thus locally sparse, aiming to improve local measures of runtime and memory. To improve those local measures, it is important to be able to compute such sparsifiers locally. We initiate the study of local algorithms for bounded degree sparsifiers in unweighted sparse graphs, focusing on the problems of vertex cover, matching, and independent set. Let \eps > 0 be a slack parameter and \alpha \ge 1 be a density parameter. We devise local algorithms for computing: 1. A (1+\eps)-vertex cover sparsifier of degree O(\alpha / \eps), for any graph of arboricity \alpha.\footnote{In a graph of arboricity \alpha the average degree of any induced subgraph is at most 2\alpha.} 2. A (1+\eps)-maximum matching sparsifier and also a (1+\eps)-maximal matching sparsifier of degree O(\alpha / \eps, for any graph of arboricity \alpha. 3. A (1+\eps)-independent set sparsifier of degree O(\alpha^2 / \eps), for any graph of average degree \alpha. Our algorithms require only a single communication round in the standard message passing model of distributed computing, and moreover, they can be simulated locally in a trivial way. As an immediate application we can extend results from distributed computing and local computation algorithms that apply to graphs of degree bounded by d to graphs of arboricity O(d / \eps) or average degree O(d^2 / \eps), at the expense of increasing the approximation guarantee by a factor of (1+\eps). In particular, we can extend the plethora of recent local computation algorithms for approximate maximum and maximal matching from bounded degree graphs to bounded arboricity graphs with a negligible loss in the approximation guarantee. The inherently local behavior of our algorithms can be used to amplify the approximation guarantee of any sparsifier in time roughly linear in its size, which has immediate applications in the area of dynamic graph algorithms. In particular, the state-of-the-art algorithm for maintaining (2-\eps)-vertex cover (VC) is at least linear in the graph size, even in dynamic forests. We provide a reduction from the dynamic to the static case, showing that if a t-VC can be computed from scratch in time T(n) in any (sub)family of graphs with arboricity bounded by \alpha, for an arbitrary t \ge 1, then a (t+\eps)-VC can be maintained with update time \frac{T(n)}{O((n / \alpha) \cdot \eps^2)}, for any \eps > 0. For planar graphs this yields an algorithm for maintaining a (1+\eps)-VC with constant update time for any constant \eps > 0.
Keywords
  • arboricity
  • bounded degree
  • local algorithm
  • sparsifier

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In Proc. 57th FOCS, pages 335-344, 2016. Google Scholar
  2. Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proc. 23rd SODA, pages 1132-1139, 2012. Google Scholar
  3. S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. H. M. Smid. Euclidean spanners: short, thin, and lanky. In Proc. of 27th STOC, pages 489-498, 1995. Google Scholar
  4. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. CoRR, abs/1711.03076, 2017. Google Scholar
  5. B. Awerbuch, A. Baratz, and D. Peleg. Cost-sensitive analysis of communication protocols. In Proc. of 9th PODC, pages 177-187, 1990. Google Scholar
  6. B. Awerbuch, A. Baratz, and D. Peleg. Efficient broadcast and light-weight spanners. Technical Report CS92-22, Weizmann Institute, October, 1992. Google Scholar
  7. Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs. J. ACM, 41(1):153-180, 1994. Google Scholar
  8. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2+ε)-approximation for vertex cover in o(logδ/ε log log δ) rounds. In Proc. PODC, pages 3-8, 2016. Google Scholar
  9. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. J. ACM, 63(3):20:1-20:45, 2016. Google Scholar
  10. S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n) update time. In Proc. of 52nd FOCS, pages 383-392, 2011. Google Scholar
  11. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n^2) time. In Proc. 28th STOC, pages 47-55, 1996. Google Scholar
  12. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Proc. 42nd ICALP, pages 167-179, 2015. Google Scholar
  13. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proc. of 26th SODA, pages 692-711, 2016. Google Scholar
  14. S. Bhattacharya, M. Henzinger, and G. F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In Proc. 26th SODA, pages 785-804, 2015. Google Scholar
  15. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In Proc. 48th STOC, pages 398-411, 2016. Google Scholar
  16. Bartlomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych. Online bipartite matching in offline time. In Proc. 55th FOCS, pages 384-393, 2014. Google Scholar
  17. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 217-226, 2016. Google Scholar
  18. Shiri Chechik. Compact routing schemes with improved stretch. In ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013, pages 33-41, 2013. Google Scholar
  19. Eden Chlamtác and Michael Dinitz. Lowest degree k-spanner: Approximation and hardness. In Proc. of APPROX/RANDOM, pages 80-95, 2014. Google Scholar
  20. Eden Chlamtac, Michael Dinitz, and Robert Krauthgamer. Everywhere-sparse spanners via dense subgraphs. In PRof. 53rd FOCS, pages 758-767, 2012. Google Scholar
  21. Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. CoRR, abs/1707.03478, 2017. Google Scholar
  22. Andrzej Czygrinow, Michal Hanckowiak, and Edyta Szymanska. Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs. In PRoc. 20th ISAAC, pages 668-678, 2009. Google Scholar
  23. G. Das, P. J. Heffernan, and G. Narasimhan. Optimally sparse spanners in 3-dimensional Euclidean space. In Proc. of 9th SOCG, pages 53-62, 1993. Google Scholar
  24. G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geometry Appl., 7(4):297-315, 1997. Google Scholar
  25. Michael Elkin and Shay Solomon. Optimal euclidean spanners: Really short, thin, and lanky. J. ACM, 62(5):35:1-35:45, 2015. Google Scholar
  26. Guy Even, Moti Medina, and Dana Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In Proc. 22th ESA, pages 394-405, 2014. Google Scholar
  27. Guy Even, Moti Medina, and Dana Ron. Distributed maximum matching in bounded degree graphs. In Proc. ICDCN, pages 18:1-18:10, 2015. Google Scholar
  28. Manuela Fischer. Improved deterministic distributed matching via rounding. CoRR, abs/1703.00900v2, 2017. Google Scholar
  29. J. Gudmundsson, C. Levcopoulos, and G. Narasimhan. Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput., 31(5):1479-1500, 2002. Google Scholar
  30. M. Gupta and R. Peng. Fully dynamic (1+ε)-approximate matchings. In Proc. of 54th FOCS, pages 548-557, 2013. Google Scholar
  31. M. Gupta and A. Sharma. An o(log(n)) fully dynamic algorithm for maximum matching in a tree. CoRR, abs/0901.2900, 2009. Google Scholar
  32. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J. Comput. Syst. Sci., 57(3):366-375, 1998. Google Scholar
  33. P. Hall. On representatives of subsets. J. London Math. Soc, 10(1):26-30, 1935. Google Scholar
  34. M. He, G. Tang, and N. Zeh. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In Proc. 25th ISAAC, pages 128-140, 2014. Google Scholar
  35. Dorit S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6(3):243-254, 1983. Google Scholar
  36. J. E. Hopcroft and R. M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. Google Scholar
  37. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  38. T. Kopelowitz, R. Krauthgamer, E. Porat, and S. Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Proc. 41st ICALP, pages 532-543, 2014. Google Scholar
  39. Frank Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 47-56, 2010. Google Scholar
  40. Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Local computation algorithms for graphs of non-constant degrees. Algorithmica, 77(4):971-994, 2017. Google Scholar
  41. Yishay Mansour and Shai Vardi. A local computation approximation scheme to maximum matching. In Proc. APPROX/RANDOM, pages 260-273, 2013. Google Scholar
  42. S. Micali and V. V. Vazirani. An O(√|V| |E|) algorithm for finding maximum matching in general graphs. In Proc. of 21st FOCS, pages 17-27, 1980. Google Scholar
  43. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 3-12, 2009. Google Scholar
  44. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proc. of 45th STOC, pages 745-754, 2013. Google Scholar
  45. K. Onak and R. Rubinfeld. Maintaining a large matching and a small vertex cover. In Proc. of 42nd STOC, pages 457-464, 2010. Google Scholar
  46. Merav Parter, David Peleg, and Shay Solomon. Local-on-average distributed tasks. In Proc. of 27th SODA, pages 220-239, 2016. Google Scholar
  47. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  48. D. Peleg and S. Solomon. Dynamic (1 + ε)-approximate matchings: A density-sensitive approach. In Proc. of 27th SODA, pages 712-729, 2016. Google Scholar
  49. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput., 18(4):740-747, 1989. Google Scholar
  50. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Prof. of ICS, pages 223-238, 2011. Google Scholar
  51. S. Solomon. Fully dynamic maximal matching in constant update time. In Proc. 57th FOCS, pages 325-334, 2016. Google Scholar
  52. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proc. 36th STOC, pages 81-90, 2004. Google Scholar
  53. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proc. of 13th SPAA, pages 1-10, 2001. Google Scholar
  54. V. V. Vazirani. An improved definition of blossoms and a simpler proof of the MV matching algorithm. CoRR, abs/1210.4594, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact