1-vs-2 cycles problem

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$ -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 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).^[1] If so, this would be optimal, as connected components can be constructed in logarithmic rounds in this model.^[2]

This assumption implies similar communication lower bounds for several other problems in this computational model, including single-linkage clustering^[1] and geometric minimum spanning trees.^[3] 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.^[4]

References

^ ^a ^b Yaroslavtsev, Grigory; Vadapalli, Adithya (2018), "Massively parallel algorithms and hardness for single-linkage clustering under $\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
^ 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, doi:10.1109/ICDE.2013.6544813
^ 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, doi:10.1145/2591796.2591805
^ 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

[yv-1] Yaroslavtsev, Grigory; Vadapalli, Adithya (2018), "Massively parallel algorithms and hardness for single-linkage clustering under $\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

[rmcs-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, doi:10.1109/ICDE.2013.6544813

[anoy-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, doi:10.1145/2591796.2591805

[rvw-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

[1]

[2]

[3]

[4]