论文标题
多项式时间算法，以确定（几乎）密集的常规图（几乎）汉密尔顿
A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
论文作者
论文摘要
我们给出了一种多项式时间算法，用于检测非常长的常规图中很长的周期。 Specifically, we show that, given $α\in (0,1)$, there exists a $c=c(α)$ such that the following holds: there is a polynomial-time algorithm that, given a $D$-regular graph $G$ on $n$ vertices with $D\geq αn$, determines whether $G$ contains a cycle on at least $n - c$ vertices.如果我们删除密度或规律性条件，则该问题将变成NP库。该算法结合了极端图理论和光谱分区的工具以及一些进一步的算法成分。
We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given $α\in (0,1)$, there exists a $c=c(α)$ such that the following holds: there is a polynomial-time algorithm that, given a $D$-regular graph $G$ on $n$ vertices with $D\geq αn$, determines whether $G$ contains a cycle on at least $n - c$ vertices. The problem becomes NP-complete if we drop either the density or the regularity condition. The algorithm combines tools from extremal graph theory and spectral partitioning as well as some further algorithmic ingredients.
