[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Distributed Computation of the Minimum Triangle Edge Transversal

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

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

  • 220 Accesses

Abstract

The distance of a graph from being triangle-free is a fundamental graph parameter, counting the number of edges that need to be removed from a graph in order for it to become triangle-free. Its corresponding computational problem is the classic minimum triangle edge transversal problem, and its normalized value is the baseline for triangle-freeness testing algorithms. While triangle-freeness testing has been successfully studied in the distributed setting, computing the distance itself in a distributed setting is unknown, to the best of our knowledge, despite being well-studied in the centralized setting.

This work addresses the computation of the minimum triangle edge transversal in distributed networks. We show with a simple warm-up construction that this is a global task, requiring \(\varOmega (D)\) rounds even in the \(\textsf{LOCAL}\) model with unbounded messages, where D is the diameter of the network. However, we show that approximating this value can be done much faster. A \((1+\epsilon )\)-approximation can be obtained in \(\text {poly}\log {n}\) rounds, where n is the size of the network graph. Moreover, faster approximations can be obtained, at the cost of increasing the approximation factor to roughly 3, by a reduction to the minimum hypergraph vertex cover problem. With a time overhead of the maximum degree \(\varDelta \), this can also be applied to the \(\textsf{CONGEST}\) model, in which messages are bounded.

Our key technical contribution is proving that computing an exact solution is “as hard as it gets” in \(\textsf{CONGEST}\), requiring a near-quadratic number of rounds. Because this problem is an edge selection problem, as opposed to previous lower bounds that were for node selection problems, major challenges arise in constructing the lower bound, requiring us to develop novel ingredients.

This paper takes a reduced form of the original paper. A full version is available at https://arxiv.org/abs/2402.13985 and referred in [12]. The section numbering is the same in both versions. Note that the numbering of some claims may be different in the full version.

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
$34.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 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    It was suggested to us to replace this part of the construction with a different underlying graph with \(\varTheta (n)\) nodes, which is known to have \(\varTheta (n^2/2^{\sqrt{\log n}})\) edge-disjoint triangles [43]. Such a graph would give a smaller lower bound, but an even more severe issue is that it is not clear how to incorporate it in a construction that will allow the MTET size to correspond to the solution to the set disjointness input.

References

  1. Abboud, A., Censor-Hillel, K., Khoury, S.: Near-linear lower bounds for distributed distance computations, even in sparse networks. In: Gavoille, C., Ilcinkas, D. (eds.) Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, 27–29 September 2016. Proceedings. Lecture Notes in Computer Science, vol. 9888, pp. 29–42. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53426-7_3

  2. Abboud, A., Censor-Hillel, K., Khoury, S., Lenzen, C.: Fooling views: a new lower bound technique for distributed computations under congestion. Distrib. Comput. 33, 545–559 (2020). https://doi.org/10.1007/s00446-020-00373-4

  3. Abboud, A., Censor-Hillel, K., Khoury, S., Paz, A.: Smaller cuts, higher lower bounds. ACM Trans. Algorithms 17(4), 30:1–30:40 (2021). https://doi.org/10.1145/3469834, https://doi.org/10.1145/3469834

  4. Bacrach, N., Censor-Hillel, K., Dory, M., Efron, Y., Leitersdorf, D., Paz, A.: Hardness of distributed optimization. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 238–247 (2019)

    Google Scholar 

  5. Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68(4), 702–732 (2004). https://doi.org/10.1016/j.jcss.2003.11.006

  6. Ben-Basat, R., Even, G., Kawarabayashi, K., Schwartzman, G.: Optimal distributed covering algorithms. In: Robinson, P., Ellen, F. (eds.) Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, 29 July–2 August 2019, pp. 104–106. ACM (2019). https://doi.org/10.1145/3293611.3331577

  7. Brakerski, Z., Patt-Shamir, B.: Distributed discovery of large near-cliques. Distrib. Comput. 24(2), 79–89 (2011). https://doi.org/10.1007/s00446-011-0132-x

  8. Censor-Hillel, K.: Distributed subgraph finding: progress and challenges. CoRR abs/2203.06597 (2022). https://doi.org/10.48550/arXiv.2203.06597

  9. Censor-Hillel, K., Fischer, E., Schwartzman, G., Vasudev, Y.: Fast distributed algorithms for testing graph properties. Distrib. Comput. 32(1), 41–57 (2019). https://doi.org/10.1007/S00446-018-0324-8

  10. Censor-Hillel, K., Fischer, O., Gonen, T., Gall, F.L., Leitersdorf, D., Oshman, R.: Fast distributed algorithms for girth, cycles and small subgraphs. CoRR abs/2101.07590 (2021). https://arxiv.org/abs/2101.07590

  11. Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. Distrib. Comput. 32(6), 461–478 (2019). https://doi.org/10.1007/s00446-016-0270-2

  12. Censor-Hillel, K., Khoury, M.: On distributed computation of the minimum triangle edge transversal (2024). https://arxiv.org/abs/2402.13985

  13. Censor-Hillel, K., Leitersdorf, D., Turner, E.: Sparse matrix multiplication and triangle listing in the congested clique model. Theor. Comput. Sci. 809, 45–60 (2020). https://doi.org/10.1016/j.tcs.2019.11.006

  14. Censor-Hillel, K., Leitersdorf, D., Vulakh, D.: Deterministic near-optimal distributed listing of cliques. In: Proceedings of the Symposium on Principles of Distributed Computation (PODC), pp. 271–280 (2022)

    Google Scholar 

  15. Chang, Y.J., Pettie, S., Saranurak, T., Zhang, H.: Near-optimal distributed triangle enumeration via expander decompositions. J. ACM 68(3), 1–36 (2021)

    Article  MathSciNet  Google Scholar 

  16. Chang, Y., Saranurak, T.: Deterministic distributed expander decomposition and routing with applications in distributed derandomization. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 377–388 (2020). https://doi.org/10.1109/FOCS46700.2020.00043

  17. Das Sarma, A., et al.: Distributed verification and hardness of distributed approximation. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 363-372. Association for Computing Machinery, New York (2011). https://doi.org/10.1145/1993636.1993686

  18. Dolev, D., Lenzen, C., Peled, S.: “tri, tri again": finding triangles and small subgraphs in a distributed setting - (extended abstract). In: Aguilera, M.K. (ed.) Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, 16–18 October 2012. Proceedings. Lecture Notes in Computer Science, vol. 7611, pp. 195–209. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33651-5_14

  19. Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Halldórsson, M.M., Dolev, S. (eds.) ACM Symposium on Principles of Distributed Computing, PODC 2014, Paris, France, 15–18 July 2014, pp. 367–376. ACM (2014). https://doi.org/10.1145/2611462.2611493

  20. Eden, T., Fiat, N., Fischer, O., Kuhn, F., Oshman, R.: Sublinear-time distributed algorithms for detecting small cliques and even cycles. Distrib. Comput. 35(3), 207–234 (2022). https://doi.org/10.1007/s00446-021-00409-3

    Article  MathSciNet  Google Scholar 

  21. Erdös, P., Gallai, T., Tuza, Z.: Covering and independence in triangle structures. Discret. Math. 150(1–3), 89–101 (1996). https://doi.org/10.1016/0012-365X(95)00178-Y

    Article  MathSciNet  Google Scholar 

  22. Even, G., et al.: Three notes on distributed property testing. In: Richa, A.W. (ed.) 31st International Symposium on Distributed Computing, DISC 2017, Vienna, Austria, 16–20 October 2017. LIPIcs, vol. 91, pp. 15:1–15:30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017). https://doi.org/10.4230/LIPIcs.DISC.2017.15

  23. Fischer, O., Gonen, T., Kuhn, F., Oshman, R.: Possibilities and impossibilities for distributed subgraph detection. In: Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 153–162 (2018). https://doi.org/10.1145/3210377.3210401

  24. Fraigniaud, P., Olivetti, D.: Distributed detection of cycles. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 153–162 (2017)

    Google Scholar 

  25. Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17–19 January 2012, pp. 1150–1162. SIAM (2012). https://doi.org/10.1137/1.9781611973099.91

  26. Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: Hatami, H., McKenzie, P., King, V. (eds.) Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19–23 June 2017, pp. 784–797. ACM (2017). https://doi.org/10.1145/3055399.3055471

  27. Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653–750 (1998). https://doi.org/10.1145/285055.285060

  28. Hirvonen, J., Rybicki, J., Schmid, S., Suomela, J.: Large cuts with local algorithms on triangle-free graphs. Electron. J. Comb. 24(4), P4.21 (2017). http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p21

  29. Holzer, S., Pinsker, N.: Approximation of distances and shortest paths in the broadcast congest clique. In: Anceaume, E., Cachin, C., Potop-Butucaru, M.G. (eds.) 19th International Conference on Principles of Distributed Systems, OPODIS 2015, Rennes, France, 14–17 December 2015. LIPIcs, vol. 46, pp. 6:1–6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015). https://doi.org/10.4230/LIPIcs.OPODIS.2015.6

  30. Huang, D., Pettie, S., Zhang, Y., Zhang, Z.: The communication complexity of set intersection and multiple equality testing. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1715–1732 (2020). https://doi.org/10.1137/1.9781611975994.105

  31. Izumi, T., Gall, F.L.: Triangle finding and listing in CONGEST networks. In: Schiller, E.M., Schwarzmann, A.A. (eds.) Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, 25–27 July 2017, pp. 381–389. ACM (2017).https://doi.org/10.1145/3087801.3087811

  32. Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discret. Math. 5(4), 545–557 (1992). https://doi.org/10.1137/0405044

    Article  MathSciNet  Google Scholar 

  33. Kortsarz, G., Langberg, M., Nutov, Z.: Approximating maximum subgraphs without short cycles. SIAM J. Discret. Math. 24(1), 255–269 (2010). https://doi.org/10.1137/09074944X

    Article  MathSciNet  Google Scholar 

  34. Krivelevich, M.: On a conjecture of tuza about packing and covering of triangles. Discret. Math. 142(1-3), 281–286 (1995). https://doi.org/10.1016/0012-365X(93)00228-W

  35. Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  37. Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput. 35(1), 120–131 (2005). https://doi.org/10.1137/S0097539704441848

    Article  MathSciNet  Google Scholar 

  38. Pandurangan, G., Robinson, P., Scquizzato, M.: On the distributed complexity of large-scale graph computations. ACM Trans. Parallel Comput. 8(2), 7:1–7:28 (2021). https://doi.org/10.1145/3460900

  39. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)

    Book  Google Scholar 

  40. Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427–1442 (2000). https://doi.org/10.1137/S0097539700369740

  41. Pettie, S., Su, H.: Fast distributed coloring algorithms for triangle-free graphs. In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 681–693 (2013)

    Google Scholar 

  42. Razborov, A.A.: On the distributional complexity of disjointness. In: Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP), pp. 249–253 (1990)

    Google Scholar 

  43. Ruzsa, I.Z., Szemerédi, E.: Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18(939-945), 2 (1978)

    Google Scholar 

Download references

Acknowledgements

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement no. 755839, and from ISF grant 529/23. The authors thank Seri Khoury for many useful discussions.

Author information

Authors and Affiliations

  1. Technion, Haifa, Israel

    Keren Censor-Hillel & Majd Khoury

Authors
  1. Keren Censor-Hillel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Majd Khoury
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Majd Khoury .

Editor information

Editors and Affiliations

  1. Faculty of Data and Decision Sciences, Technion – Israel Institute of Technolog, Haifa, Israel

    Yuval Emek

Rights and permissions

Reprints and permissions

Copyright information

© 2024 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

Censor-Hillel, K., Khoury, M. (2024). On Distributed Computation of the Minimum Triangle Edge Transversal. In: Emek, Y. (eds) Structural Information and Communication Complexity. SIROCCO 2024. Lecture Notes in Computer Science, vol 14662. Springer, Cham. https://doi.org/10.1007/978-3-031-60603-8_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-60603-8_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-60602-1

  • Online ISBN: 978-3-031-60603-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics