In the theory of parallel algorithms, the 1-vs-2 cycles problem concerns a simplified case of

graph connectivity In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

. The input to the problem is a 2-regular graph, forming either a single connected

n

-vertex cycle or two disconnected

n/2

-vertex cycles. The problem is to determine whether the input has one or two cycles. The 1-vs-2 cycles conjecture or 2-cycle conjecture is an unproven

computational hardness assumption In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (unconditi ...

asserting that solving the 1-vs-2 cycles problem in the

massively parallel communication In the study of parallel algorithms, the massively parallel communication model or MPC model is a theoretical model of computing, intended as an abstraction for parallel computing systems that use frameworks such as MapReduce, and frequently ap ...

model requires at least a logarithmic number of rounds of communication, even for a randomized algorithm that succeeds with high probability (having a polynomially small failure probability). If so, this would be optimal, as connected components can be constructed in logarithmic rounds in this model. This assumption implies similar communication

lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less th ...

s for several other problems in this computational model, including

single-linkage clustering In statistics, single-linkage clustering is one of several methods of hierarchical clustering. It is based on grouping clusters in bottom-up fashion (agglomerative clustering), at each step combining two clusters that contain the closest pair of el ...

and geometric

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...

s. However, proving the 1-vs-2 cycles conjecture may be difficult, as any non-constant lower bound for the number of rounds for this problem would imply that the parallel complexity class NC¹ does not contain all problems in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

, which would be a significant advance on current knowledge.

References

{{reflist, refs= {{citation , last1 = Andoni , first1 = Alexandr , last2 = Nikolov , first2 = Aleksandar , last3 = Onak , first3 = Krzysztof , last4 = Yaroslavtsev , first4 = Grigory , editor-last = Shmoys , editor-first = David B. , contribution = Parallel algorithms for geometric graph problems , contribution-url = http://grigory.us/files/publications/ANOY-STOC14.pdf , doi = 10.1145/2591796.2591805 , pages = 574–583 , publisher = Association for Computing Machinery , title = Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 – June 03, 2014 , year = 2014, arxiv = 1401.0042 , isbn = 978-1-4503-2710-7 {{citation , last1 = Rastogi , first1 = Vibhor , last2 = Machanavajjhala , first2 = Ashwin , last3 = Chitnis , first3 = Laukik , last4 = Sarma , first4 = Anish Das , editor1-last = Jensen , editor1-first = Christian S. , editor2-last = Jermaine , editor2-first = Christopher M. , editor3-last = Zhou , editor3-first = Xiaofang , contribution = Finding connected components in map-reduce in logarithmic rounds , doi = 10.1109/ICDE.2013.6544813 , pages = 50–61 , publisher = IEEE Computer Society , title = 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8–12, 2013 , year = 2013, arxiv = 1203.5387 , isbn = 978-1-4673-4910-9 {{citation , last1 = Roughgarden , first1 = Tim , last2 = Vassilvitskii , first2 = Sergei , last3 = Wang , first3 = Joshua R. , doi = 10.1145/3232536 , issue = 6 , journal = Journal of the ACM , mr = 3882585 , article-number = 41 , title = Shuffles and circuits (on lower bounds for modern parallel computation) , volume = 65 , year = 2018 {{citation , last1 = Yaroslavtsev , first1 = Grigory , last2 = Vadapalli , first2 = Adithya , editor1-last = Dy , editor1-first = Jennifer G. , editor2-last = Krause , editor2-first = Andreas , contribution = Massively parallel algorithms and hardness for single-linkage clustering under

\ell_p

distances , contribution-url = https://proceedings.mlr.press/v80/yaroslavtsev18a.html , pages = 5596–5605 , series = Proceedings of Machine Learning Research , title = Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10–15, 2018 , volume = 80 , year = 2018 Graph connectivity Computational problems in graph theory Computational hardness assumptions