# Hidden Hamiltonian Cycle Recovery via Linear Programming

arXiv: https://arxiv.org/abs/1804.05436 · HTML: https://mlsanity.com/paper/1804.05436/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2018.

## Built on by (most cited first, 8 of 8)

- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)
- [Recovery thresholds for hidden weighted sparse graphs](https://mlsanity.com/paper/2606.14335/) (2026)

## Abstract (arXiv)

We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an n-vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are independent and distributed according to calPn for edges in the cycle and calQn otherwise. This formulation is motivated by a problem in genome assembly, where the goal is to order a set of contigs (genome subsequences) according to their positions on the genome using long-range linking measurements between the contigs. Computing the maximum likelihood estimate in this model reduces to a Traveling Salesman Problem (TSP). Despite the NP-hardness of TSP, we show that a simple linear programming (LP) relaxation, namely the fractional 2-factor (F2F) LP, recovers the hidden Hamiltonian cycle with high probability as n → ∞ provided that αn - log n → ∞, where αn triangleq -2 log int √d Pn d Qn is the R'enyi divergence of order frac12. This condition is information-theoretically optimal in the sense that, under mild distributional assumptions, αn ≥ (1+o(1)) log n is necessary for any algorithm to succeed regardless of the computational cost. Departing from the usual proof techniques based on dual witness construction, the analysis relies on the combinatorial characterization (in particular, the half-integrality) of the extreme points of the F2F polytope. Represented as bicolored multi-graphs, these extreme points are further decomposed into simpler "blossom-type" structures for the large deviation analysis and counting arguments. Evaluation of the algorithm on real data shows improvements over existing approaches.