Misplaced Pages

1-vs-2 cycles problem

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Unsolved problem in parallel algorithms

In the theory of parallel algorithms, the 1-vs-2 cycles problem concerns a simplified case of graph connectivity. The input to the problem is a 2-regular graph, forming either a single connected n {\displaystyle n} -vertex cycle or two disconnected n / 2 {\displaystyle 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 asserting that solving the 1-vs-2 cycles problem in the massively parallel communication 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 bounds for several other problems in this computational model, including single-linkage clustering and geometric minimum spanning trees. 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, which would be a significant advance on current knowledge.

References

  1. ^ Yaroslavtsev, Grigory; Vadapalli, Adithya (2018), "Massively parallel algorithms and hardness for single-linkage clustering under ℓ p {\displaystyle \ell _{p}} distances", in Dy, Jennifer G.; Krause, Andreas (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10–15, 2018, Proceedings of Machine Learning Research, vol. 80, pp. 5596–5605
  2. Rastogi, Vibhor; Machanavajjhala, Ashwin; Chitnis, Laukik; Sarma, Anish Das (2013), "Finding connected components in map-reduce in logarithmic rounds", in Jensen, Christian S.; Jermaine, Christopher M.; Zhou, Xiaofang (eds.), 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8–12, 2013, IEEE Computer Society, pp. 50–61, arXiv:1203.5387, doi:10.1109/ICDE.2013.6544813, ISBN 978-1-4673-4910-9
  3. Andoni, Alexandr; Nikolov, Aleksandar; Onak, Krzysztof; Yaroslavtsev, Grigory (2014), "Parallel algorithms for geometric graph problems" (PDF), in Shmoys, David B. (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 – June 03, 2014, Association for Computing Machinery, pp. 574–583, arXiv:1401.0042, doi:10.1145/2591796.2591805, ISBN 978-1-4503-2710-7
  4. Roughgarden, Tim; Vassilvitskii, Sergei; Wang, Joshua R. (2018), "Shuffles and circuits (on lower bounds for modern parallel computation)", Journal of the ACM, 65 (6) 41, doi:10.1145/3232536, MR 3882585
Categories:
1-vs-2 cycles problem Add topic