On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST Model
share
It is known that, for every k≥ 2, C_2k-freeness can be decided by a generic Monte-Carlo algorithm running in n^1-1/Θ(k^2) rounds in the CONGEST model. For 2≤ k≤ 5, faster Monte-Carlo algorithms do exist, running in O(n^1-1/k) rounds, based on upper bounding the number of messages to be forwarded, and aborting search sub-routines for which this number exceeds certain thresholds. We investigate the possible extension of these threshold-based algorithms, for the detection of larger cycles. We first show that, for every k≥ 6, there exists an infinite family of graphs containing a 2k-cycle for which any threshold-based algorithm fails to detect that cycle. Hence, in particular, neither C_12-freeness nor C_14-freeness can be decided by threshold-based algorithms. Nevertheless, we show that {C_12,C_14}-freeness can still be decided by a threshold-based algorithm, running in O(n^1-1/7)= O(n^0.857…) rounds, which is faster than using the generic algorithm, which would run in O(n^1-1/22)≃ O(n^0.954…) rounds. Moreover, we exhibit an infinite collection of families of cycles such that threshold-based algorithms can decide ℱ-freeness for every ℱ in this collection.
READ FULL TEXT