Detecting cliques in CONGEST networks

DOI10.1007/S00446-019-00368-WMaRDI QIDQ2220401zbMATH OpenOpenAlexWikidataFDO

Authors Artur Czumaj, Christian Konrad

Publication date 22 January 2021

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1807.01070

zbMATH Keywords

CONGEST modellower boundsset-disjointnesssubgraph detectiontwo-party communication

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11) Graph theory (including graph drawing) in computer science (68R10)

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_l$ 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_l$ requires $Omega(sqrtn/b)$ communication rounds, for every $4lellesqrtn$, and $Omega(n/(lb))$ rounds for every $lgesqrtn$, 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.

Recommendations

• Detecting cliques in CONGEST networks
• On the power of the congested clique model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Triangle Finding and Listing in CONGEST Networks

Cites work

• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Communication Complexity
• Deterministic subgraph detection in broadcast CONGEST
• Distributed Computing: A Locality-Sensitive Approach
• Distributed discovery of large near-cliques
• Distributed triangle detection via expander decomposition
• Distributed verification and hardness of distributed approximation
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Lower bounds for subgraph detection in the CONGEST model
• On the power of the congested clique model
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• The Probabilistic Communication Complexity of Set Intersection
• Three notes on distributed property testing
• Triangle Finding and Listing in CONGEST Networks

Cited in

(19)

• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Finding disjoint dense clubs in a social network
• A note on improved results for one round distributed clique listing
• On the power of the congested clique model
• Lower bounds for subgraph detection in the CONGEST model
• Distributed Discovery of Large Near-Cliques
• Detecting the number of clusters in a network
• On the detection of transitive clusters in undirected networks
• Detecting cliques in CONGEST networks
• Distributed detection of cliques in dynamic networks
• The communication complexity of set intersection and multiple equality testing
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• On designing networks resilient to clique blockers
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Deterministic near-optimal distributed listing of cliques
• Fast approximate counting of cycles
• Deterministic expander routing: faster and more versatile
• Finding clique clusters with the highest betweenness centrality
• Very large cliques are easy to detect

This page was built for publication: Detecting cliques in CONGEST networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220401)