Abstract
The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in \({\mathcal {O}}^{*}(\alpha^{n})\) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses \({\mathcal {O}}^{*}(1.657^{n})\) time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses \({\mathcal {O}}^{*}(1.6818^{n})\) time and exponential space, and one algorithm that uses \({\mathcal {O}}^{*}(1.8878^{n})\) time and polynomial space.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian path problem. Inf. Process. Lett. 47(4), 203–207 (1993)
Björklund, A.: Determinant sums for undirected hamiltonicity. In: 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pp. 173–182. IEEE Computer Society, Los Alamitos (2010)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The travelling salesman problem in bounded degree graphs. In: Aceto, L., Damgaard, I., Goldberg, L.A., Halldorsson, M.M., Ingolfsdottir, A., Walukiewicz, I. (eds.) 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). Lecture Notes in Computer Science, vol. 5125, pp. 198–209. Springer, Berlin (2008)
Broersma, H.J., Fomin, F.V., van ’t Hof, P., Paulusma, D.: Fast exact algorithms for hamiltonicity in claw-free graphs. In: Paul, C., Habib, M. (eds.) 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009) Lecture Notes in Computer Science, vol. 5911, pp. 44–53. Springer, Berlin (2009)
Broersma, H.J., Paulusma, D.: Computing sharp 2-factors in claw-free graphs. J. Discrete Algorithms 8(3), 321–329 (2010)
Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)
Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming on H-minor-free graphs. In: Teng, S.-H. (ed.) Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp. 631–640. ACM-SIAM, Philadelphia (2008)
Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions. Algorithmica 58(3), 790–810 (2010)
Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61–81 (2007)
Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs—a survey. Discrete Math. 164(1–3), 87–147 (1997)
Garey, M.R., Johnson, D.S.: Computers Intractability. Freeman, New York (1979)
Gebauer, H.: Finding and enumerating Hamilton cycles in 4-regular graphs. Theor. Comput. Sci. 412(35), 4579–4591 (2011)
Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
Harary, F., Nash-Williams, C.St.J.A.: On Eulerian and Hamiltonian graphs and line graphs. Can. Math. Bull. 8(6), 701–709 (1965)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196–210 (1962)
Iwama, K., Nakashima, T.: An improved exact algorithm for cubic graph TSP. In: Lin, G. (ed.) 13th Annual International Computing and Combinatorics Conference (COCOON 2007). Lecture Notes in Computer Science, vol. 4598, pp. 108–117. Springer, Berlin (2007)
Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1(2), 49–51 (1982)
Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the traveling salesman problem. In: Proceedings of the ACM Annual Conference (ACM 1977), pp. 294–300. ACM Press, New York (1977)
Kuipers, E.J., Veldman, H.J.: Recognizing claw-free Hamiltonian graphs with large minimum degree. Memorandum 1437, University of Twente, Enschede (1998)
Li, M., Corneil, D.G., Mendelsohn, E.: Pancyclicity and NP-completeness in planar graphs. Discrete Appl. Math. 98(3), 219–225 (2000)
Lonc, Z.: On the complexity of some edge-partition problems for graphs. Discrete Appl. Math. 70(2), 177–183 (1996)
Müller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156(1–3), 291–298 (1996)
Oberly, D.J., Simić, S.K., Sumner, D.P.,: Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian. J. Graph Theory 3(4), 351–356 (1979)
Roussopoulos, N.D.: A max {m,n} algorithm for determining the graph H from its line graph G. Inf. Process. Lett. 2(4), 108–112 (1973)
Ryjáček, Z.: On a closure concept in claw-free graphs. J. Comb. Theory, Ser. B 70(2), 217–224 (1997)
Thomassen, C., Toft, B.: Non-separating induced cycles in graphs. J. Comb. Theory, Ser. B 31(2), 199–224 (1981)
Woeginger, G.J.: Open problems around exact algorithms. Discrete Appl. Math. 156(3), 397–405 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this paper has been presented at WG 2009 [4].
H. Broersma, P. van ’t Hof, and D. Paulusma have been supported by EPSRC (EP/D053633/1).
Rights and permissions
About this article
Cite this article
Broersma, H., Fomin, F.V., van ’t Hof, P. et al. Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs. Algorithmica 65, 129–145 (2013). https://doi.org/10.1007/s00453-011-9576-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9576-4