Algorithms for finding an induced cycle in planar graphs
Algorithms for finding an induced cycle in planar graphs
复制标题
DOI：
10.1007/s00493-010-2499-x
复制
发表时间：
2010-11
期刊：
影响因子：
1.1
通讯作者：
K. Kawarabayashi;Yusuke Kobayashi
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;Yusuke Kobayashi
本文考虑了求一个通过k个给定顶点的诱导圈的问题，我们称之为诱导圈问题。发现诱导圈的重要性源于这样一个事实，即完美图的精确刻画需要理解没有奇诱导圈及其补图的图的结构。最近几年来，这方面的研究取得了很大的进展，特别是在[6]中解决了强完美图猜想。关于完美图的识别问题，在文献[4]中，发现奇洞及其补洞是一个长期存在的问题，而在文献[2]中，发现通过两个给定顶点的诱导圈是NP-完全的。然而，如果输入图被约束为平面且k是固定的，则诱导圈问题可以在多项式时间内求解[11]-[13]。特别地，McDiarmid，Reed，Schrijver和Shepherd [14]给出了一个O（n ~ 2）时间的算法，其中n是输入图的顶点数，本文的主要结果是在以下意义上改进了他们的结果：1.顶点数允许是非平凡的超常数，直到.更准确地说，当，那么ICP可以在O（n2+ n2）时间内解决，任何n2> 0.2。时间复杂度是线性的ifkis固定的。我们注意到线性时间算法（第二个结果）与第一个结果无关。让我们观察到ifkis作为输入的一部分，那么问题仍然是NP完全的，所以我们需要对k施加一些条件。
In this paper, we consider the problem of finding an induced cycle passing throughkgiven vertices, which we call theinduced cycle problem. The significance of finding induced cycles stems from the fact that a precise characterization of perfect graphs would require understanding the structure of graphs without an odd induced cycle and its complement. There has been huge progress in the recent years, especially, the Strong Perfect Graph Conjecture was solved in [6]. Concerning recognition of perfect graphs, there had been a long-standing open problem for detecting an odd hole and its complement, and finally this was solved in [4].Unfortunately, the problem of finding an induced cycle passing through two given vertices is NP-complete in a general graph [2]. However, if the input graph is constrained to be planar andkis fixed, then the induced cycle problem can be solved in polynomial time [11]–[13]. In particular, an O(n2) time algorithm is given for the casek=2 by McDiarmid, Reed, Schrijver and Shepherd [14], wherenis the number of vertices of the input graph.Our main results in this paper are to improve their result in the following sense.1.The number of verticeskis allowed to be non-trivially super constant number, up to. More precisely, when, then the ICP can be solved in O(n2+ɛ) time for anyɛ> 0.2.The time complexity is linear ifkis fixed.We note that the linear time algorithm (the second result) is independent from the first result.Let us observe that ifkis as a part of the input, then the problem is still NP-complete, and so we need to impose some condition onk.