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 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.