Title: Recovering a hidden Hamiltonian cycle via linear programming
Authors: Yihong Wu - Yale University (United States) [presenting]
Abstract: The problem of hidden Hamiltonian cycle recovery is introduced, 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 $P_n$ for edges in the cycle and $Q_n$ 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. Computing the maximum likelihood estimate in this model reduces to the 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 \to \infty$ at the exact information-theoretic optimal threshold. 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. Evaluation of the algorithm on real data shows improvements over existing approaches.