Finding even cycles faster via capped k-walks
Finding even cycles faster via capped k-walks
复制标题
通过 capped k-walks 更快地找到均匀循环
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Morten Stöckel
中科院分区：
文献类型：
--
作者：
Søren Dahlgaard;M. B. T. Knudsen;Morten Stöckel
图中圈的寻找是算法图论中的一个基本问题。本文考虑了在n个结点m条边的无向图G中，当k≥ 2时，求出并报告一个长为2k的圈的问题.邦迪和Simonovits [J.组合论，1974]的一个经典结果暗示，如果m ≥ 100 kn 1 +1/k，则G包含一个2k-圈，进一步暗示，只需要考虑m = O（n1+1/k）的图。以前最著名的算法是由于Yuster和Zwick [J. Discrete Math 1997]的O（n2）算法以及Alon et. [1997年]。我们提出了一个算法，使用O（m2 k/（k+1））的时间，并找到一个2k-循环，如果存在。当m = Θ（n1+1/k）时，时间复杂度为O（n2）。当发现4-圈，我们的新的界限与阿隆等。例如，而对于每一个k>2，我们的新界产生了m的多项式改进。Yuster和Zwick指出，“推测O（n2）是n的最佳可能界是合理的”。我们证明了“条件最优性”：如果这个假设成立，那么我们的O（m2 k/（k+1））算法也是紧的。此外，一个民俗约简意味着，没有组合算法可以确定一个图是否包含一个6-圈的时间为O（m3/2-ε），对于任何ε>0，除非布尔矩阵乘法可以在O（n3-ε′）的时间内组合解决，对于某些ε′ > 0，这被广泛认为是错误的。再加上我们的主要结果，这给出了紧密的界限，找到6个周期的组合，也分开了复杂性，找到4个和6个周期的证据表明，指数m的运行时间确实应该增加与k。在我们的算法中的关键成分是一个新的概念，封顶k-散步，这是散步的长度为k，只访问节点根据一个固定的顺序。我们的主要技术贡献是一个复杂的分析证明了几个属性，这样的步行可能是独立的利益。
Finding cycles in graphs is a fundamental problem in algorithmic graph theory. In this paper, we consider the problem of finding and reporting a cycle of length 2k in an undirected graph G with n nodes and m edges for constant k≥ 2. A classic result by Bondy and Simonovits [J. Combinatorial Theory, 1974] implies that if m ≥ 100k n1+1/k, then G contains a 2k-cycle, further implying that one needs to consider only graphs with m = O(n1+1/k). Previously the best known algorithms were an O(n2) algorithm due to Yuster and Zwick [J. Discrete Math 1997] as well as a O(m2-(1+⌈ k/2 ⌉-1)/(k+1)) algorithm by Alon et. al. [Algorithmica 1997]. We present an algorithm that uses O( m2k/(k+1) ) time and finds a 2k-cycle if one exists. This bound is O(n2) exactly when m = Θ(n1+1/k). When finding 4-cycles our new bound coincides with Alon et. al., while for every k>2 our new bound yields a polynomial improvement in m. Yuster and Zwick noted that it is "plausible to conjecture that O(n2) is the best possible bound in terms of n". We show "conditional optimality": if this hypothesis holds then our O(m2k/(k+1)) algorithm is tight as well. Furthermore, a folklore reduction implies that no combinatorial algorithm can determine if a graph contains a 6-cycle in time O(m3/2-ε) for any ε>0 unless boolean matrix multiplication can be solved combinatorially in time O(n3-ε′) for some ε′ > 0, which is widely believed to be false. Coupled with our main result, this gives tight bounds for finding 6-cycles combinatorially and also separates the complexity of finding 4- and 6-cycles giving evidence that the exponent of m in the running time should indeed increase with k. The key ingredient in our algorithm is a new notion of capped k-walks, which are walks of length k that visit only nodes according to a fixed ordering. Our main technical contribution is an involved analysis proving several properties of such walks which may be of independent interest.