Top

Published in:

2018 | OriginalPaper | Chapter

Connectivity and Minimum Cut Approximation in the Broadcast Congested Clique

Authors : Tomasz Jurdziński, Krzysztof Nowicki

Published in: Structural Information and Communication Complexity

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we present two graph algorithms in the Broadcast Congested Clique model. In this model, there are n players, which communicate in synchronous rounds. Each player represents a single node of the input graph; initially each player knows the set of edges incident to his node. In each round of communication each node can broadcast a single b–bit message to all other nodes; usually \(b \in {\mathcal {O}}(\log n)\). The goal is to compute some function of the input graph.

The first result we present is the first sub-logarithmic deterministic algorithm finding a maximal spanning forest of an n node graph in the Broadcast Congested Clique, which requires only \({\mathcal {O}}(\log n / \log \log n)\) rounds. The second result is a randomized \(1 + \epsilon \) approximation algorithm finding the minimum cut of an n node graph, which requires only \({\mathcal {O}}(\log n)\) maximal spanning forest computations. In the Broadcast Congested Clique this approach, combined with the new maximal spanning forest algorithm, yields an \({\mathcal {O}}(\log ^2 n / \log \log n)\) round algorithm. Additionally, it may be applied to different models, i.e. in the multi-pass semi-streaming model it allows to reduce required memory by \(\varTheta (\log n)\) factor, with only \({\mathcal {O}}(\log ^* n)\) passes over the data stream.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On Knowledge and Communication Complexity in Distributed Systems

next chapter Biased Clocks: A Novel Approach to Improve the Ability To Perform Predicate Detection with O(1) Clocks

In this paper authors present an algorithm for semi–streaming model, however the result applies to the \(\mathsf {Broadcast}\) \(\mathsf {Congested}\) \(\mathsf {Clique}\).

Note that deactivation of components of degree \(<s\) at the end of a phase does not guarantee that degrees of all components are \(\ge s\) at the beginning of the next phase. This is caused by the fact that deactivation of some components might decrease degrees of components which remain active (degrees are calculated only among active nodes).

Authors of papers [1, 2] have inconsistent way of defining space complexity, i.e. c connectivity in [1] requires \({\mathcal {O}}(c n \log ^3 n)\) ‘space’, when referenced in [2] it only requires \({\mathcal {O}}(c n \log ^2 n)\) ‘space’. Here we go with the approach from [1], which seems to count bits.

Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17–19 January 2012, pp. 459–467 (2012)CrossRef

Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: PODS 2012, pp. 5–14. ACM (2012)

Becker, F., Montealegre, P., Rapaport, I., Todinca, I.: The simultaneous number-in-hand communication model for networks: private coins, public coins and determinism. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 83–95. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09620-9_8CrossRefMATH

Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: PODC 2014, pp. 367–376 (2014)

Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2), 207–216 (2005)MathSciNetCrossRef

Ghaffari, M., Parter, M.: MST in log-star rounds of congested clique. In: Proceedings of PODC 2016 (2016)

Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward optimal bounds in the congested clique: graph connectivity and MST. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, 21–23 July 2015, pp. 91–100 (2015)

Jurdzinski, T., Nowicki, K.: Brief announcement: on connectivity in the broadcast congested clique. In: 31st International Symposium on Distributed Computing, DISC 2017, Vienna, Austria, 16–20 October 2017, pp. 54:1–54:4 (2017)

Jurdziński, T., Nowicki, K.: MST in O(1) rounds of congested clique. In: SODA 2018, pp. 2620–2632 (2018)CrossRef

10.

Karger, D.R.: Random sampling in cut, flow, and network design problems. In: ACM Symposium on Theory of Computing (STOC), pp. 648–657 (1994)

11.

Kari, J., Matamala, M., Rapaport, I., Salo, V.: Solving the Induced Subgraph problem in the randomized multiparty simultaneous messages model. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 370–384. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25258-2_26CrossRef

12.

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)MathSciNetCrossRef

13.

Montealegre, P., Todinca, I.: Brief announcement: deterministic graph connectivity in the broadcast congested clique. In: Proceedings of PODC 2016 (2016)

14.

Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discret. Math. 5(1), 54–66 (1992)MathSciNetCrossRef

15.

Nešetřil, J., Milková, E., Nešetřilová, H.: Otakar Boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discret. Math. 233(1), 3–36 (2001)MathSciNetCrossRef

16.

Nishizeki, T., Poljak, S.: Highly connected factors with a small number of edges. Preprint (1989)

Title: Connectivity and Minimum Cut Approximation in the Broadcast Congested Clique
Authors: Tomasz Jurdziński
Krzysztof Nowicki
Publisher: Springer International Publishing
Book: Structural Information and Communication Complexity
Print ISBN: 978-3-030-01324-0

Electronic ISBN: 978-3-030-01325-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-01325-7_28

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner