Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

ABSTRACT

In this paper, we consider the problem of finding an induced cycle passing through k given vertices, which we call the induced cycle problem. The significance of finding induced cycles stems from the fact that precise characterization of perfect graphs would require structures 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 and k is fixed, then the induced cycle problem can be solved in polynomial time [13, 14, 16].

In particular, an O(n²) time algorithm is given for the case k = 2 by McDiarmid, Reed, Schrijver and Shepherd [18], where n is 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 vertices k is allowed to be non-trivially super constant number, up to k = o((log n/log log n)^2/3). More precisely, when k = o((log n/log log n)^2/3), then the ICP in planar graphs can be solved in O(n^2+ε) time for any ε>0.

2. The time complexity is linear if the given graph is planar and k is fixed.

3. The above results are extended to graphs embedded in a fixed surface.

We note that the linear time algorithm (the second result) is independent from the first result.

Let us point out that we give the first polynomial time algorithm for the problem for the bounded genus case. In fact, our proof gives a short proof of a result announced in [20] (without complete proof) which gives a linear time algorithm for the disjoint paths problem for fixed k for the bounded genus case. We also extend this result to the induced disjoint paths problem.

Let us observe that if k is as a part of the input, then the problem is still NP-complete, and so we need to impose some condition on k.

REFERENCES

• 1: Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
• 2: Dan Bienstock, On the complexity of testing for odd holes and induced odd paths, Discrete Mathematics, v.90 n.1, p.85-92, June 1991 [doi>10.1016/0012-365X(91)90098-M]
• 3: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 4: Maria Chudnovsky , Gérard Cornuéjols , Xinming Liu , Paul Seymour , Kristina Vušković, Recognizing Berge Graphs, Combinatorica, v.25 n.2, p.143-186, March 2005 [doi>10.1007/s00493-005-0012-8]
• 5: Maria Chudnovsky , Ken-ichi Kawarabayashi , Paul Seymour, Detecting even holes, Journal of Graph Theory, v.48 n.2, p.85-111, February 2005 [doi>10.1002/jgt.v48:2]
• 6: M. Chudnovsky, N. Robertson, P. D. Seymour and R. Thomas: The strong perfect graph theorem, Ann. of Math., 64 (2006), pp. 51--219.
• 7: Michele Conforti , Gérard Cornuéjols , Ajai Kapoor , Kristina Vušković, Even-hole-free graphs part I: Decomposition theorem, Journal of Graph Theory, v.39 n.1, p.6-49, January 2002 [doi>10.1002/jgt.v39:1]
• 8: Michele Conforti , Gérard Cornuéjols , Ajai Kapoor , Kristina Vušković, Even-hole-free graphs part II: Recognition algorithm, Journal of Graph Theory, v.40 n.4, p.238-266, August 2002 [doi>10.1002/jgt.v40:4]
• 9: Erik D. Demaine , Fedor V. Fomin , Mohammadtaghi Hajiaghayi , Dimitrios M. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, Journal of the ACM (JACM), v.52 n.6, p.866-893, November 2005 [doi>10.1145/1101821.1101823]
• 10: Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513430]
• 11: M. R. Fellows: The Robertson-Seymour Theorems: a survey of applications, Contemporary Mathematics 89, American Mathematical Society, 1987, pp. 1--18.
• 12: M. R. Fellows, J. Kratochvil, M. Middendorf and F. Pfeiffer: The complexity of induced minors and related problems, Algorithmica, 13 (1995), pp. 266--282.
• 13: K. Kawarabayashi and Y. Kobayashi: A linear time algorithm for the induced disjoint paths problem in planar graphs, manuscript.
• 14: K. Kawarabayashi and Y. Kobayashi: The induced disjoint paths problem, Proc. the 13th Integer Programming and Combinatorial Optimization (LNCS 5035), 2008, pp. 47--61.
• 15: Ken-ichi Kawarabayashi , Bojan Mohar, Graph and map isomorphism and all polyhedral embeddings in linear time, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374443]
• 16: Y. Kobayashi: An extension of the disjoint paths problem, METR 2007-14, Department of Mathematical Informatics, University of Tokyo (2006).
• 17: B. Lévêque, D. Lin, F. Maffray and N. Trotignon: Detecting induced subgraphs, Disc. Appl. Math., to appear.
• 18: C. McDiarmid , B. Reed , A. Schrijver , B. Shepherd, Induced circuits in planar graphs, Journal of Combinatorial Theory Series B, v.60 n.2, p.169-176, March 1994 [doi>10.1006/jctb.1994.1011]
• 19: B. Mohar and C. Thomassen: Graphs on Surfaces, The Johns Hopkins University Press, Baltimore and London, 2001.
• 20: Bruce Reed, Rooted routing in the plane, Discrete Applied Mathematics, v.57 n.2-3, p.213-227, Feb. 24, 1995 [doi>10.1016/0166-218X(94)00104-L]
• 21: B. A. Reed, N. Robertson, A. Schrijver and P. D. Seymour: Finding disjoint trees in planar graphs in linear time, Contemporary Mathematics 147, American Mathematical Society, 1993, pp. 295--301.
• 22: Neil Robertson , P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, Journal of Combinatorial Theory Series B, v.45 n.2, p.212-254, Oct. 1988 [doi>10.1016/0095-8956(88)90070-6]
• 23: Neil Robertson , P. D. Seymour, Graph minors. XI.: circuits on a surface, Journal of Combinatorial Theory Series B, v.60 n.1, p.72-106, Jan. 1994 [doi>10.1006/jctb.1994.1007]
• 24: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 25: N. Robertson and P. D. Seymour: Graph minors. XXII. Irrelevant vertices in linkage problems, manuscript.
• 26: Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
• 27: Carsten Thomassen, A simpler proof of the excluded minor theorem for higher surfaces, Journal of Combinatorial Theory Series B, v.70 n.2, p.306-311, July 1997 [doi>10.1006/jctb.1997.1761]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms