Detecting cliques in CONGEST networks
- PDF / 622,972 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 100 Downloads / 187 Views
Detecting cliques in CONGEST networks Artur Czumaj1 · Christian Konrad2 Received: 29 December 2018 / Accepted: 9 December 2019 © The Author(s) 2019
Abstract The problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given graph H , the input network contains a subgraph isomorphic to H or not. We investigate this problem for H being a clique K in the classical distributed CONGEST model, where the communication topology is the same as the topology of the underlying network, and with limited communication bandwidth on the links. √ Our first and main result is a lower bound, showing that detecting K requires Ω( n/b) communication rounds, for every √ √ 4 ≤ ≤ n, and Ω(n/(b)) rounds for every ≥ n, where b is the bandwidth of the communication links. This result is obtained by using a reduction to the set disjointness problem in the framework of two-party communication complexity. We complement our lower bound with a two-party communication protocol for listing all cliques in the input graph, which up to constant factors communicates the same number of bits as our lower bound for K 4 detection. This demonstrates that our lower bound cannot be improved using the two-party communication framework. Keywords CONGEST model · Subgraph detection · Lower bounds · Two-party communication · Set-disjointness
1 Introduction We study the problem of detecting network structures in a distributed environment, which is a fundamental problem in modern computing. Our focus is on the subgraph detection problem, in which for a given graph H , one wants to determine whether the network graph G contains a subgraph isomorphic to H or not. We investigate this problem for H being a clique K for ≥ 4. The nowadays classical distributed CONGEST model (see, e.g., [21]) is a variant of the classical LOCAL model of distributed computation (where in each round network nodes Research partially supported by the Centre for Discrete Mathematics and its Applications (DIMAP), by EPSRC Award EP/D063191/1, and by EPSRC award EP/N011163/1. Most of work on this paper was carried out while C.K. was at the University of Warwick.
B
Christian Konrad [email protected] Artur Czumaj [email protected]
1
Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick, Coventry, UK
2
Department of Computer Science, University of Bristol, Bristol, UK
can send through all incident links messages of unrestricted size) with limited communication bandwidth. The distributed system is represented as a network (undirected graph) G = (V , E) with n = |V | nodes, where network nodes execute distributed algorithms in synchronous rounds, and the nodes collaborate to solve a graph problem with input G. Further, every node has a unique identifier from {0, . . . , poly(n)}. In any single round, all nodes can: (i) perform an unlimited amount of local computation, (ii) send a possibly
Data Loading...
