The planted k-factor problem

DOI10.1088/1751-8121/ABEE9DarXiv2010.13700MaRDI QIDQ6352272FDOQ6352272

Authors: Gabriele Sicuro, Lenka Zdeborová 

Publication date: 26 October 2020

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.

Mathematics Subject Classification ID

Inference from spatial processes (62M30) Random graphs (graph-theoretic aspects) (05C80)

This page was built for publication: The planted $k$-factor problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6352272)