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 ${\displaystyle n}$-vertex cycle or two disconnected ${\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.