Loading...
research article
The planted k-factor problem
April 30, 2021
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 traveling 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.
Use this identifier to reference this record
Type
research article
Web of Science ID
WOS:000637829900001
Authors
Publication date
2021-04-30
Publisher
Volume
54
Issue
17
Article Number
175002
Peer reviewed
REVIEWED
Available on Infoscience
May 22, 2021