2026-07-22T14:19:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8644 2024-03-06T10:42:11Z ddc:004 open_access

Lower Bounds for Subgraph Detection in the CONGEST Model Gonen, Tzlil Oshman, Rotem subgraph freeness CONGEST lower bounds In the subgraph-freeness problem, we are given a constant-sized 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 subgraph-freeness 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 subgraph-freeness in the CONGEST model for two classes of subgraphs. The first class contains any graph obtained by starting from a 2-connected 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 k-cycle. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tzlil Gonen and Rotem Oshman 2018 Is Part Of LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2017.6 urn:nbn:de:0030-drops-86445 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.6 eng https://creativecommons.org/licenses/by/3.0/legalcode