# Deterministic subgraph detection in broadcast CONGEST

arXiv: https://arxiv.org/abs/1705.10195 · HTML: https://mlsanity.com/paper/1705.10195/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2017.

## Built on by (most cited first, 2 of 2)

- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [Flood and Echo Net: Algorithmically Aligned GNNs that Generalize](https://mlsanity.com/paper/2310.06970/) (2023)

## Abstract (arXiv)

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 + log n) rounds, and 5-cycles in O(d2 + log n) 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/log n) and O(d2/log n), respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.