Hard-phase conjecture for partial graph alignment

Fix parameters $(\lambda,s)$ in the correlated Erdős–Rényi model $\mathcal{G}(n,\lambda/n,s)$. One-sided correlation detection in trees is said to fail when none of the equivalent conditions in the paper's tree-detection theorem holds, and partial recovery means achieving partial alignment of the correlated graphs. Hard-phase conjecture. If one-sided correlation detection in trees fails, then no polynomial-time algorithm achieves partial recovery. The paper gives a non-empty parameter region where one-sided tree detection fails but partial graph alignment is possible in non-polynomial time; the conjecture would therefore imply that the hard phase is non-empty.