We present a deterministic algorithm for finding a minimum‑cost Hamiltonian cycle in undirected graphs with arbitrary real edge weights, assuming the graph contains an independent set of size at least $\alpha n$ for any fixed $\alpha$ with $\frac{3}{7}<\alpha\le\frac{1}{2}$. The running time is $O^*(\gamma(\alpha)^n)$ where the explicit constant $\gamma(\alpha)<2$. For bipartite graphs the bound improves to $O^*((1+2\sqrt{2})^{n/2})\approx O^*(1.957^n)$.
The algorithm relies on a restricted Held–Karp dynamic program. State enumeration exploits structural properties of minimum‑cost assignments that arise from a regular triangulation of the product of simplices $\Delta^{k}\times\Delta^{\ell}$. This geometric insight allows us to prune a large fraction of infeasible subproblems, achieving a sub‑exponential speed‑up.
Key steps of the algorithm are:
- Independent‑set preprocessing: Choose an independent set $I$ of size $\alpha n$ and treat its vertices as “safe” nodes that never cause path crossings in the DP.
- Restricted state definition: Keep only partial paths on the complement of $I$ that form matchings and satisfy the triangulation constraints.
- Recursive transition: For each valid state, update the path length using the solution of a minimum‑cost assignment problem, guaranteeing optimality of the Hamiltonian cycle.
- Solution reconstruction: After DP completion, backtrack to retrieve the full Hamiltonian cycle.
Theoretical analysis shows that as $\alpha$ approaches $\frac{1}{2}$, $\gamma(\alpha)$ drops to around $1.9$, substantially better than the classic $O^*(2^n)$ brute‑force bound. Preliminary experiments (not detailed here) confirm noticeable speed‑ups on medium‑size graphs.
Review