SpringerLink
Log in

Distributed Half-Integral Matching and Beyond

  • Conference paper
  • First Online:
Structural Information and Communication Complexity (SIROCCO 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13892))

Abstract

By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires \(\varOmega (\log ^* n)\) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from \(\{0, \frac{1}{2}, 1\}\). We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree \(\varDelta = 2d\), and any distributed graph algorithm with round complexity \(T(\varDelta )\) that only depends on \(\varDelta \) and is independent of n, we show that the algorithm has to use fractional values with a denominator at least \(2^d\). We give a new algorithm that shows that this is also sufficient.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pp. 82–93. ACM Press (1980). https://doi.org/10.1145/800141.804655

  2. Åstrand, M., Floréen, P., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: A local 2-approximation algorithm for the vertex cover problem. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 191–205. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04355-0_21

    Chapter  Google Scholar 

  3. Åstrand, M., Suomela, J.: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010), pp. 294–302. ACM Press (2010). https://doi.org/10.1145/1810479.1810533

  4. Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. J. ACM 68(5), 1–30 (2021). https://doi.org/10.1145/3461458

    Article  MathSciNet  MATH  Google Scholar 

  5. Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981). https://doi.org/10.1016/0196-6774(81)90020-1

    Article  MathSciNet  MATH  Google Scholar 

  6. Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), pp. 321–330 (2012). https://doi.org/10.1109/FOCS.2012.60

  7. Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 1–45 (2016). https://doi.org/10.1145/2903137

    Article  MathSciNet  MATH  Google Scholar 

  8. Fischer, M.: Improved deterministic distributed matching via rounding. Distrib. Comput. 33, 279–291 (2020). https://doi.org/10.1007/s00446-018-0344-4

    Article  MathSciNet  MATH  Google Scholar 

  9. Göös, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. J. ACM 60(5), 1–23 (2013). https://doi.org/10.1145/2528405

    Article  MathSciNet  MATH  Google Scholar 

  10. Göös, M., Hirvonen, J., Suomela, J.: Linear-in-\(\varDelta \) lower bounds in the LOCAL model. Distrib. Comput. 30(5), 325–338 (2015). https://doi.org/10.1007/s00446-015-0245-8

    Article  MathSciNet  MATH  Google Scholar 

  11. Hanckowiak, M., Karonski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. SIAM J. Discret. Math. 15(1), 41–57 (2001). https://doi.org/10.1137/S0895480100373121

    Article  MathSciNet  MATH  Google Scholar 

  12. Hirvonen, J., Suomela, J.: Distributed maximal matching: greedy is optimal. In: Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2012), pp. 165–174. ACM Press (2012). https://doi.org/10.1145/2332432.2332464

  13. Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 77–80 (1986). https://doi.org/10.1016/0020-0190(86)90144-4

    Article  MathSciNet  MATH  Google Scholar 

  14. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992). https://doi.org/10.1137/0221015

    Article  MathSciNet  MATH  Google Scholar 

  15. Mayer, A., Naor, M., Stockmeyer, L.: Local computations on static and dynamic graphs. In: Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS 1995), pp. 268–278. IEEE (1995). https://doi.org/10.1109/ISTCS.1995.377023

  16. Naor, M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discret. Math. 4(3), 409–412 (1991). https://doi.org/10.1137/0404036

    Article  MathSciNet  MATH  Google Scholar 

  17. Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97–100 (2001). https://doi.org/10.1007/PL00008932

    Article  MATH  Google Scholar 

  18. Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14, 97–100 (2001). https://doi.org/10.1007/PL00008932

    Article  MATH  Google Scholar 

  19. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics (2000). https://doi.org/10.1137/1.9780898719772

  20. Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Heidelberg (2003)

    MATH  Google Scholar 

  21. Yamashita, M., Kameda, T.: Computing on anonymous networks: part I—characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7(1), 69–89 (1996). https://doi.org/10.1109/71.481599

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported in part by the Academy of Finland, Grant 333837. We would like to thank the anonymous reviewers for their helpful feedback, and the members of Aalto Distributed Algorithms group for discussions.

Author information

Authors and Affiliations

  1. Aalto University, Espoo, Finland

    Sameep Dahal & Jukka Suomela

Authors
  1. Sameep Dahal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jukka Suomela
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jukka Suomela .

Editor information

Editors and Affiliations

  1. National Autonomous University of Mexico, Mexico, Mexico

    Sergio Rajsbaum

  2. Gran Sasso Science Institute, L’Aquila, Italy

    Alkida Balliu

  3. Arizona State University, Tempe, AZ, USA

    Joshua J. Daymude

  4. Gran Sasso Science Institute, L’Aquila, Italy

    Dennis Olivetti

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Dahal, S., Suomela, J. (2023). Distributed Half-Integral Matching and Beyond. In: Rajsbaum, S., Balliu, A., Daymude, J.J., Olivetti, D. (eds) Structural Information and Communication Complexity. SIROCCO 2023. Lecture Notes in Computer Science, vol 13892. Springer, Cham. https://doi.org/10.1007/978-3-031-32733-9_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-32733-9_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-32732-2

  • Online ISBN: 978-3-031-32733-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation