1-vs-2 cycles problem

Template:Short description Template:Use dmy dates Template:Use list-defined references Template:CS1 config 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).Template:R If so, this would be optimal, as connected components can be constructed in logarithmic rounds in this model.Template:R

This assumption implies similar communication lower bounds for several other problems in this computational model, including single-linkage clusteringTemplate:R and geometric minimum spanning trees.Template:R 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.Template:R