research-article
Authors: Pierre Fraigniaud, Maël Luce, and Ioan Todinca
Volume 996, Issue C
Published: 09 July 2024 Publication History
- 0citation
- 0
- Downloads
Metrics
Total Citations0Total Downloads0Last 12 Months0
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
- View Options
- References
- Media
- Tables
- Share
Abstract
It is known that, for every k ≥ 2, C 2 k-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 F-freeness for every F in this collection.
References
[1]
H. Broersma, P.A. Golovach, D. Paulusma, J. Song, Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time, Theor. Comput. Sci. 423 (2012) 1–10.
[2]
D. Neuen, Isomorphism testing for graphs excluding small topological subgraphs, in: 33rd ACM Symposium on Discrete Algorithms (SODA), 2022, pp. 1411–1434.
[3]
D. Peleg, Distributed Computing: a Locality-Sensitive Approach, SIAM, 2000.
[4]
A. Drucker, F. Kuhn, R. Oshman, On the power of the congested clique model, in: 33rd ACM Symposium on Principles of Distributed Computing (PODC), 2014, pp. 367–376.
[5]
O. Fischer, T. Gonen, F. Kuhn, R. Oshman, Possibilities and impossibilities for distributed subgraph detection, in: 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018, pp. 153–162.
[6]
K. Censor-Hillel, O. Fischer, T. Gonen, F.L. Gall, D. Leitersdorf, R. Oshman, Fast distributed algorithms for girth, cycles and small subgraphs, in: 34th International Symposium on Distributed Computing (DISC), in: LIPIcs, vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 33:1–33:17.
[7]
N. Alon, R. Yuster, U. Zwick, Color-coding, J. ACM 42 (4) (1995) 844–856.
Digital Library
[8]
T. Eden, N. Fiat, O. Fischer, F. Kuhn, R. Oshman, Sublinear-time distributed algorithms for detecting small cliques and even cycles, Distrib. Comput. 35 (3) (2022) 207–234.
[9]
Korhonen, J.H.; Rybicki, J. (2017): Deterministic subgraph detection in broadcast congest. arXiv preprint arXiv:1705.10195.
[10]
K. Censor-Hillel, P. Kaski, J.H. Korhonen, C. Lenzen, A. Paz, J. Suomela, Algebraic methods in the congested clique, in: 34th ACM Symposium on Principles of Distributed Computing (PODC), 2015, pp. 143–152.
[11]
Censor-Hillel, K. (2022): Distributed subgraph finding: progress and challenges. arXiv preprint arXiv:2203.06597.
[12]
G. Even, O. Fischer, P. Fraigniaud, T. Gonen, R. Levi, M. Medina, P. Montealegre, D. Olivetti, R. Oshman, I. Rapaport, I. Todinca, Three notes on distributed property testing, in: 31st International Symposium on Distributed Computing (DISC), in: LIPIcs, vol. 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 15:1–15:30.
[13]
P. Fraigniaud, D. Olivetti, Distributed detection of cycles, ACM Trans. Parallel Comput. 6 (3) (2019) 12:1–12:20.
[14]
P. Kővári, V.T. Sós, P. Turán, On a Problem of Zarankiewicz, Colloquium Mathematicum, vol. 3, Polska Akademia Nauk, 1954, pp. 50–57.
Recommendations
- On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST Model
Structural Information and Communication Complexity
Abstract
It is known that, for every , -freeness can be decided by a generic Monte-Carlo algorithm running in rounds in the congest model. For , faster Monte-Carlo algorithms do exist, running in rounds, based on upper bounding the number of messages to ...
Read More
- Even-Cycle Detection in the Randomized and Quantum CONGEST Model
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing
We show that, for every k ≥ 2, C2k-freeness can be decided in O(n1--1/k) rounds in the CONGEST model by a randomized Monte-Carlo distributed algorithm with one-sided error probability 1/3. This matches the best round-complexities of previously known ...
Read More
- Threshold counters with increments and decrements
A threshold counter is a shared data structure that assumes integer values. It provides two operations: Increment changes the current counter value from v to v+1, while Read returns the value [v/w], where v is the current counter value and w is a fixed ...
Read More
Comments
Information & Contributors
Information
Published In
Theoretical Computer Science Volume 996, Issue C
May 2024
103 pages
ISSN:0304-3975
Issue’s Table of Contents
Copyright © 2024.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 09 July 2024
Author Tags
- Cycle-freeness
- Distributed computing
- Congest model
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Other Metrics
View Author Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
Media
Figures
Other
Tables
