1-vs-2 cycles problem

From HandWiki
Short description: 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-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 NC1 does not contain all problems in polynomial time, which would be a significant advance on current knowledge.[4]

References

  1. ↑ 1.0 1.1 Yaroslavtsev, Grigory; Vadapalli, Adithya (2018), "Massively parallel algorithms and hardness for single-linkage clustering under ℓp distances", in Dy, Jennifer G.; Krause, Andreas, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10–15, 2018, Proceedings of Machine Learning Research, 80, pp. 5596–5605, https://proceedings.mlr.press/v80/yaroslavtsev18a.html 
  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, 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, ISBN 978-1-4673-4910-9 
  3. ↑ Andoni, Alexandr; Nikolov, Aleksandar; Onak, Krzysztof; Yaroslavtsev, Grigory (2014), "Parallel algorithms for geometric graph problems", in Shmoys, David B., 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, ISBN 978-1-4503-2710-7, http://grigory.us/files/publications/ANOY-STOC14.pdf 
  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), doi:10.1145/3232536 



Retrieved from "https://handwiki.org/wiki/index.php?title=1-vs-2_cycles_problem&oldid=3984452"