我们给出了一种确定性算法，用于在无向图中寻找最小费用哈密顿环。该图的边权可以是任意实数，并且图中至少存在一个大小为 $\alpha n$ 的独立集，其中 $\alpha$ 为任意固定常数满足 $\frac{3}{7}<\alpha\le\frac{1}{2}$。算法的时间复杂度为 $O^*(\gamma(\alpha)^n)$，其中显式常数 $\gamma(\alpha)<2$。在二分图的特殊情形下，复杂度提升至 $O^*((1+2\sqrt{2})^{n/2})\approx O^*(1.957^n)$。
核心思路基于受限的 Held–Karp 动态规划。我们对状态空间进行精细枚举，利用最小费用指派问题在 $\Delta^{k}\times\Delta^{\ell}$（两个单纯形的笛卡尔积）上的正则三角剖分所产生的结构性质。该几何视角帮助我们剔除大量不可能的子问题，从而实现指数级别的加速。
算法的主要步骤如下：
- 独立集预处理：选取大小为 $\alpha n$ 的独立集 $I$，将其视为“安全点”，在后续的 DP 中固定不参与路径交叉。
- 受限状态定义：仅保留那些在 $I$ 的补集上形成匹配且满足三角剖分约束的子路径集合。
- 递推转移：对每个合法状态，使用最小费用指派的解来更新路径长度，确保哈密顿环的最小化。
- 结果恢复：在 DP 完成后回溯得到完整的哈密顿环。
该算法的理论分析表明，随着 $\alpha$ 接近 $\frac{1}{2}$ 时，$\gamma(\alpha)$ 趋近于 $1.9$ 左右，显著优于传统的 $O^*(2^n)$ 暴力搜索。实验（未在本文中详述）亦显示在中等规模图上有可观的加速效果。
点评