论文标题
Dirac定理的算法扩展
Algorithmic Extensions of Dirac's Theorem
论文作者
论文摘要
在1952年，狄拉克（Dirac）证明了以下定理，其中关于长顶点的长期循环：每个$ n $ vertex $ 2 $ 2 $ - 连接的图形$ g $，带有最低顶点$δ\ geq 2 $包含一个至少$ \ min \ min \ min \ {2δ，n \} $ Vertices的周期。特别是，如果$δ\ geq n/2 $，则$ g $是哈密顿量。 Dirac定理的证明是建设性的，它产生了一种计算多项式时间的循环的算法。 Dirac定理的组合结合在以下意义上是紧密的。有2个连接的图形不包含长度超过$2δ+1 $的周期。此外，还有非哈米尔顿图的所有顶点，但其中一个至少$ n/2 $之一。这自然会引起以下算法问题。对于$ k \ geq 1 $， （a）确定2个连接图是否包含长度至少$ \ min \ {2δ+k，n \} $的循环有多困难？ （b）确定图形$ g $是哈密顿量是多么困难，当$ g $的至少$ n -k $顶点至少是$ n/2 -k $时？ Fomin，Golovach，Lokshtanov，Panolan，Saurabh和Zehavi提出了第一个问题。第二个问题是由于Jansen，Kozma和Nederlof造成的。即使对于$ k = 1 $的非常特殊的情况，也存在多项式时间算法的存在，决定$ g $是否包含长度至少$ \ min \ {2Δ+1，n \} $的循环。我们通过证明DIRAC定理的以下算法概括来解决这两个问题：如果除$ 2 $ 2 $连接的图形$ g $的$ k $顶点以外的所有内容至少是$δ$，那么确定$ g $的时间至少具有$ \ $ \ min \ min \ {2Δ+k，n \} $是否均可完成。 $ 2^{\ MATHCAL {O}（K）} \ CDOT N^{\ MATHCAL {O}（1）} $。 DIRAC定理的算法概括的证明基于新的图理论结果，这本身就是有趣的。
In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every $n$-vertex $2$-connected graph $G$ with minimum vertex degree $δ\geq 2$ contains a cycle with at least $\min\{2δ,n\}$ vertices. In particular, if $δ\geq n/2$, then $G$ is Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an algorithm computing the corresponding cycle in polynomial time. The combinatorial bound of Dirac's theorem is tight in the following sense. There are 2-connected graphs that do not contain cycles of length more than $2δ+1$. Also, there are non-Hamiltonian graphs with all vertices but one of degree at least $n/2$. This prompts naturally to the following algorithmic questions. For $k\geq 1$, (A) How difficult is to decide whether a 2-connected graph contains a cycle of length at least $\min\{2δ+k,n\}$? (B) How difficult is to decide whether a graph $G$ is Hamiltonian, when at least $n - k$ vertices of $G$ are of degrees at least $n/2-k$? The first question was asked by Fomin, Golovach, Lokshtanov, Panolan, Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof. Even for a very special case of $k=1$, the existence of a polynomial-time algorithm deciding whether $G$ contains a cycle of length at least $\min\{2δ+1,n\}$ was open. We resolve both questions by proving the following algorithmic generalization of Dirac's theorem: If all but $k$ vertices of a $2$-connected graph $G$ are of degree at least $δ$, then deciding whether $G$ has a cycle of length at least $\min\{2δ+k, n\}$ can be done in time $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$. The proof of the algorithmic generalization of Dirac's theorem builds on new graph-theoretical results that are interesting on their own.
