Abstract
In the subgraphfreeness problem, we are given a constantsized graph H, and wish to de termine whether the network graph contains H as a subgraph or not. Until now, the only lower bounds on subgraphfreeness known for the CONGEST model were for cycles of length greater than 3; here we extend and generalize the cycle lower bound, and obtain polynomial lower bounds for subgraphfreeness in the CONGEST model for two classes of subgraphs.
The first class contains any graph obtained by starting from a 2connected graph H for which we already know a lower bound, and replacing the vertices of H by arbitrary connected graphs. We show that the lower bound on H carries over to the new graph. The second class is constructed by starting from a cycle Ck of length k ≥ 4, and constructing a graph H ̃ from Ck by replacing each edge {i, (i + 1) mod k} of the cycle with a connected graph Hi, subject to some constraints on the graphs H_{0}, . . . , H_{k−1}. In this case we obtain a polynomial lower bound for the new graph H ̃, depending on the size of the shortest cycle in H ̃ passing through the vertices of the original kcycle.
BibTeX  Entry
@InProceedings{gonen_et_al:LIPIcs:2018:8644,
author = {Tzlil Gonen and Rotem Oshman},
title = {{Lower Bounds for Subgraph Detection in the CONGEST Model}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {6:16:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770613},
ISSN = {18688969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8644},
URN = {urn:nbn:de:0030drops86445},
doi = {10.4230/LIPIcs.OPODIS.2017.6},
annote = {Keywords: subgraph freeness, CONGEST, lower bounds}
}
Keywords: 

subgraph freeness, CONGEST, lower bounds 
Seminar: 

21st International Conference on Principles of Distributed Systems (OPODIS 2017) 
Issue Date: 

2018 
Date of publication: 

16.03.2018 