Deterministic subgraph detection in broadcast CONGEST

DOI10.4230/LIPICS.OPODIS.2017.4zbMATH Open1487.68046arXiv1705.10195OpenAlexW2962700204MaRDI QIDQ3300802FDOQ3300802

Authors: Janne H. Korhonen, Joel Rybicki 

Publication date: 30 July 2020

Abstract: We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: -- For any constant $k$, detecting $k$-paths and trees on $k$ nodes can be done in $O(1)$ rounds. -- For any constant $k$, detecting $k$-cycles and pseudotrees on $k$ nodes can be done in $O(n)$ rounds. -- On $d$-degenerate graphs, cliques and $4$-cycles can be enumerated in $O(d+logn)$ rounds, and $5$-cycles in $O(d^2+logn)$ rounds. In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for $d$-degenerate graphs can be improved to optimal complexity $O(d/logn)$ and $O(d^2/logn)$, respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.

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

Recommendations

• Lower bounds for subgraph detection in the CONGEST model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Distributed triangle detection via expander decomposition

zbMATH Keywords

distributed computinglower boundsCONGEST modelsubgraph detection

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Distributed systems (68M14)

Cites Work

• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Narrow sieves for parameterized paths and packings
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Color-coding
• Distributed Computing: A Locality-Sensitive Approach
• Decomposition of Finite Graphs Into Forests
• A Problem in Graph Theory
• A note on the Turán function of even cycles
• Distributed Graph Coloring: Fundamentals and Recent Developments
• A parameterized view on matroid optimization problems
• Title not available (Why is that?)
• The locality of distributed symmetry breaking
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Engineering Motif Search for Large Graphs
• On the power of the congested clique model
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Distributed testing of excluded subgraphs
• Three notes on distributed property testing
• Triangle Finding and Listing in CONGEST Networks

Cited In (17)

• Distributed detection of cliques in dynamic networks
• On the power of threshold-based algorithms for detecting cycles in the CONGEST model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Lower bounds for subgraph detection in the CONGEST model
• Fast distributed algorithms for girth, cycles and small subgraphs
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Detecting cliques in CONGEST networks
• Detecting cliques in CONGEST networks
• Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
• The communication complexity of set intersection and multiple equality testing
• A note on improved results for one round distributed clique listing
• The impact of locality on the detection of cycles in the broadcast congested clique model
• Deterministic near-optimal distributed listing of cliques
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Efficient distributed source detection with limited bandwidth
• Dynamic detection of subgraphs in computer networks

This page was built for publication: Deterministic subgraph detection in broadcast CONGEST

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