Hidden Hamiltonian cycle recovery via linear programming

DOI10.1287/OPRE.2019.1886MaRDI QIDQ5130484zbMATH OpenOpenAlexWikidataFDO

Authors Vivek Bagaria, Jian Ding, David N. C. Tse, Yihong Wu, Jiaming Xu

Publication date 4 November 2020

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.05436

zbMATH Keywords

fractional 2-factor linear programminglarge deviations theorypolyhedral combinatoricstraveling salesman problem

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Linear programming (90C05) Genetics and epigenetics (92D10)

Abstract: 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 $cal{P}_n$ for edges in the cycle and $cal{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 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 $noinfty$ provided that $alph{a}_n-lognoinfty$, where $alph{a}_{n}riangleq-2logintsqrtd{P}_{n}d{Q}_n$ is the R'enyi divergence of order $frac12$. This condition is information-theoretically optimal in the sense that, under mild distributional assumptions, $alph{a}_{n}geq(1+o(1))logn$ 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.

Recommendations

• Hamiltonian Cycles and Markov Chains
• scientific article; zbMATH DE number 4123549
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Hamiltonian cycles and subsets of discounted occupational measures
• Markov chains, Hamiltonian cycles and volumes of convex bodies

Cites work

• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• A new bound for the ratio between the 2-matching problem and its linear programming relaxation
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Abundance matrices and seriation in archaeology
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Algorithms for graph partitioning on the planted partition model
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Collective dynamics of `small-world' networks
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Community detection thresholds and the weak Ramanujan property
• Convex relaxations and integrality gaps
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Exact Recovery in the Stochastic Block Model
• Finding hidden hamiltonian cycles
• scientific article; zbMATH DE number 3173999 (Why is no real title available?)
• scientific article; zbMATH DE number 1342125 (Why is no real title available?)
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• scientific article; zbMATH DE number 3249675 (Why is no real title available?)
• Information Theory of DNA Shotgun Sequencing
• Integer Programming: Methods, Uses, Computations
• Large Cliques Elude the Metropolis Process
• Large networks and graph limits
• Maximum matching and a polyhedron with 0,1-vertices
• Minimax rates of community detection in stochastic block models
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
• NON-NULL RANKING MODELS. I
• Odd Minimum Cut Sets and b-Matchings Revisited
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Paths, Trees, and Flowers
• Random Laplacian matrices and convex relaxations
• Semidefinite programming relaxations for the quadratic assignment problem
• Solution of a Large-Scale Traveling-Salesman Problem
• Stringing high-dimensional data for functional analysis
• Sum-of-squares Lower Bounds for Planted Clique
• The Traveling-Salesman Problem and Minimum Spanning Trees

Cited in

(7)

• Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem
• Iterative algorithm for discrete structure recovery
• Reconstruction of line-embeddings of graphons
• The planted k-factor problem
• The planted matching problem: sharp threshold and infinite-order phase transition
• Counting stars is constant-degree optimal for detecting any planted subgraph
• Sharp thresholds in inference of planted subgraphs

This page was built for publication: Hidden Hamiltonian cycle recovery via linear programming

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