The planted $k$-factor problem

Abstract

We consider the problem of recovering an unknown $k$-factor, hidden in a weighted random graph. For $k=1$ this is the planted matching problem, while the $k=2$ case is closely related to the planted travelling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition.

arXiv comment21 pages, 4 figures

References in corpus (10)

• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Shift in the velocity of a front due to a cut-off
• Front propagation into unstable states: Universal algebraic convergence towards uniformly translating pulled fronts
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Extremal Paths on a Random Cayley Tree
• Inference in particle tracking experiments by passing messages between images
• Group testing with Random Pools: Phase Transitions and Optimal Strategy
• On Detection and Structural Reconstruction of Small-World Random Networks
• Recovery thresholds in the sparse planted matching problem

Cited by in corpus (4)

• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Planted matching problems on random hypergraphs
• A Grand-Canonical Solution to a Class of Random Optimization Problems