Algorithms for finding an induced cycle in planar graphs (Q653839)

The induced cycle problem consists of finding an induced cycle, i.e., a cycle without a chord, passing through \(k\) given vertices. This problem is NP-complete in a general graph. In the paper the authors restrict themselves to planar graphs. For them is is proved that if \(k\) is fixed then the time complexity is linear. On the other hand if \(k\) is not fixed but \(k=o\left(\frac{\log n}{\log\log n}\right)^{\frac 23}\), where \(n\) is the number of vertices, then the induced cycle problem can be solved in \(O\left(n^{2+\varepsilon}\right)\) time for any \(\varepsilon>0\).