Let l be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length (Ω(√ log l, log log l)) in polynomial time. This implies the same bound for the longest cycle, longest vw-path and longest path. The previous best bound for longest path is length Ω((log l )2/, log log l) due to Bjorklund and Husfeldt. Our approach, which builds on Bjorklund and Husfeldt's, uses cycles to enlarge cycles. This self-reducibility allows the approximation method to be iterated.
展开▼
机译：设l为最长周期中无向图中包含给定顶点 v 的边数。我们展示了如何在多项式时间内通过长度（Ω（√log l，log log l））的 v 找到一个循环。这意味着最长的循环，最长的 vw 路径和最长的路径具有相同的界限。由于Bjorklund和Husfeldt的原因，最长路径的先前最佳界限是长度Ω（（log l） 2 /，log log 1）。我们基于Bjorklund和Husfeldt的方法，使用周期来扩大周期。这种自归约性允许迭代近似方法。
展开▼
