“All-Something-Nothing” Phase Transitions in Planted k-Factor Recovery (Extended Abstract)

摘要

This paper studies the problem of inferring a k-factor, specifically a spanning k-regular graph, planted within an Erdős–Rényi random graph 𝒢(n,λ/n). We uncover an interesting “all-something-nothing” phase transition. Specifically, we show that as the average degree λ surpasses the critical threshold of 1/k, the inference problem undergoes a transition from almost exact recovery (“all” phase) to partial recovery (“something” phase). Moreover, as λ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the “nothing” phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an “all-or-nothing” phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when λ < 1/k. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct Θ(n) many small trees of size Θ(1), whereas for establishing the algorithmic lower bound, a single large tree of size Θ(√(nlog n)) suffices.