It is known that, for every $k\geq 2$, $C_{2k}$-freeness can be decided by a generic Monte-Carlo algorithm running in $n^{1-1/\Theta(k^2)}$ rounds in the CONGEST model. For $2\leq k\leq 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\geq 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\dots})$ rounds, which is faster than using the generic algorithm, which would run in $O(n^{1-1/22})\simeq O(n^{0.954\dots})$ rounds. Moreover, we exhibit an infinite collection of families of cycles such that threshold-based algorithms can decide $\mathcal{F}$-freeness for every $\mathcal{F}$ in this collection.
翻译:关于阈值算法在 CONGEST 模型中检测循环的能力
翻译摘要
已知对于每个 $k\geq 2$,在 CONGEST 模型下,可以通过一种通用的 Monte-Carlo 算法在 $n^{1-1/\Theta(k^2)}$ 轮内判断 $C_{2k}$-freeness。 对于 $2\leq k\leq 5$,存在基于上限消息转发的阈值算法,通过优化搜索子例程的阈值数量可以在 $O(n^{1-1/k})$ 轮内完成。 我们研究扩展这些阈值算法以检测更大循环的可能性。首先,我们证明了对于每个 $k\geq 6$,存在无限个包含 $2k$个循环的图,其中任何阈值算法都无法检测到这个循环。 因此,特别地,阈值算法无法决定 $C_{12}$-freeness 和 $C_{14}$-freeness。 尽管如此,我们证明 $\{C_{12},C_{14}\}$-freeness 可以通过阈值算法来检测,在 $O(n^{1-1/7})= O(n^{0.857\dots})$ 轮内运行,快于使用通用算法的速度,其运行时间为 $O(n^{1-1/22})\simeq O(n^{0.954\dots})$ 轮。此外,我们展示了一系列与循环有关的无限族,使得阈值算法可以检测到该集合中所有的 $\mathcal{F}$-freeness。