Deterministic subgraph detection in broadcast CONGEST

DOI10.4230/LIPICS.OPODIS.2017.4MaRDI QIDQ3300802zbMATH OpenOpenAlexFDO

Authors Janne H. Korhonen, Joel Rybicki

Publication date 30 July 2020

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

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)

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.

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

Cites work

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

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
• Detecting cliques in CONGEST networks
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Detecting cliques in CONGEST networks
• Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
• A note on improved results for one round distributed clique listing
• The communication complexity of set intersection and multiple equality testing
• The impact of locality on the detection of cycles in the broadcast congested clique model
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Deterministic near-optimal distributed listing of cliques
• 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)