Detecting graphs with induced cycles in limited-bandwidth communication networks
Loading...
Date
2023-08-23
Authors
Zapp, Timothy
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The subgraph detection problem is a fundamental problem in distributed algorithms
that asks the nodes of a communication network G to determine if that communication
network contains a specific graph P as a subgraph. Recent work in this
area has largely been focused on the case where the nodes have limited bandwidth
and thus cannot communicate arbitrarily, which is part of a larger movement in
distributed algorithms to reduce the amount of communication that our algorithms
require.
We show that, if P is a graph containing an induced cycle of length at least 4,
then detecting a rainbow copy of P (in terms of vertex colourings or edge colourings)
takes at least Ω(n/ log n) in the CONGEST model. Motivated by this result, we go
on to show that, if P is a necklace graph containing an odd cycle of length at least 5,
then detecting a copy of P takes at least Ω(n/ log n) rounds in the CONGEST model.
Finally, we discuss techniques for proving similar results when P is a necklace graph
containing all even cycles or a 3-cycle, and highlight the difficulties in doing so.
Description
Keywords
CONGEST, Subgraph detection, Distributed computing, Induced subgraphs, Limited-bandwidth communication networks, Lower bounds