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.

The planted k-factor problem / Sicuro G.; Zdeborova L.. - In: JOURNAL OF PHYSICS. A, MATHEMATICAL AND THEORETICAL. - ISSN 1751-8113. - ELETTRONICO. - 54:17(2021), pp. 175002.1-175002.22. [10.1088/1751-8121/abee9d]

The planted k-factor problem

Sicuro G.;
2021

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 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.
2021
The planted k-factor problem / Sicuro G.; Zdeborova L.. - In: JOURNAL OF PHYSICS. A, MATHEMATICAL AND THEORETICAL. - ISSN 1751-8113. - ELETTRONICO. - 54:17(2021), pp. 175002.1-175002.22. [10.1088/1751-8121/abee9d]
Sicuro G.; Zdeborova L.
File in questo prodotto:
File Dimensione Formato  
Sicuro_2021_J._Phys._A__Math._Theor._54_175002.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 1.23 MB
Formato Adobe PDF
1.23 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/958740
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact