[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time \(n^{\mathcal {O}(k)}\). This improves the naive algorithm that runs in time \(n^{\mathcal {O}(k^2)}\) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time \(n^{o(k)}\) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308–340 (1991)

    Article  MathSciNet  Google Scholar 

  2. Bergougnoux, B., Kanté, M.M.: More applications of the d-neighbor equivalence: connectivity and acyclicity constraints. In: 27th Annual European Symposium on Algorithms, ESA 2019, pp. 17:1–17:14. Munich/Garching, Germany, September 9–11, 2019. https://doi.org/10.4230/LIPIcs.ESA.2019.17

  3. Bergougnoux, B., Kanté, M.M., Kwon, O.: An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width. In: Algorithms and Data Structures—15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31–August 2, 2017, Proceedings, pp. 121–132 (2017)

  4. Bodlaender, H.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1–2), 1–45 (1998)

    Article  MathSciNet  Google Scholar 

  5. Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inform. Comput. 243, 86–111 (2015)

    Article  MathSciNet  Google Scholar 

  6. Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7(5&6), 555–581 (1992)

    Article  MathSciNet  Google Scholar 

  7. Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66–76 (2013)

    Article  MathSciNet  Google Scholar 

  8. Courcelle, B.: The monadic second-order logic of graphs IV: definability properties of equational graphs. Ann. Pure Appl. Log. 49(3), 193–255 (1990)

    Article  MathSciNet  Google Scholar 

  9. Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Volume 138 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2012). A language-theoretic approach, with a foreword by Maurice Nivat

    Book  Google Scholar 

  10. Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218–270 (1993)

    Article  MathSciNet  Google Scholar 

  11. Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)

    Article  MathSciNet  Google Scholar 

  12. Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109(1–2), 49–82 (1993)

    Article  MathSciNet  Google Scholar 

  13. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1–3), 77–114 (2000)

    Article  MathSciNet  Google Scholar 

  14. Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time (extended abstract). In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pp. 150–159. IEEE Computer Society, Los Alamitos, CA (2011)

  15. Diestel, R.: Graph Theory. Number 173 in Graduate Texts in Mathematics, 3rd edn. Springer, Berlin (2005)

    Google Scholar 

  16. Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Graph-theoretic concepts in computer science (Boltenhagen, 2001). Volume 2204 of Lecture Notes in Computer Science, pp. 117–128. Springer, Berlin (2001)

  17. Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math. 23(2), 909–939 (2009)

    Article  MathSciNet  Google Scholar 

  18. Fleischner, H.: Eulerian Graphs and Related Topics, vol. 1. Elsevier, Amsterdam (1990)

    MATH  Google Scholar 

  19. Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941–1956 (2010)

    Article  MathSciNet  Google Scholar 

  20. Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541–1563 (2014)

    Article  MathSciNet  Google Scholar 

  21. Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Clique-width III: hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms 15(1), 9:1–9:27 (2019)

    MathSciNet  MATH  Google Scholar 

  22. Ganian, R., Hliněný, P., Obdržálek, J.: Clique-width: when hard does not mean impossible. In: 28th International Symposium on Theoretical Aspects of Computer Science. Volume 9 of LIPIcs Leibniz International Proceedings in Informatics, pp. 404–415. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2011)

  23. Gurski, F.: A comparison of two approaches for polynomial time algorithms computing basic graph parameters. CoRR (2008). arXiv:0806.4073

  24. Hliněný, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012–1032 (2008)

    Article  MathSciNet  Google Scholar 

  25. Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Appl. Math. 126(2–3), 197–221 (2003)

    Article  MathSciNet  Google Scholar 

  26. Kotzig, A.: Moves without forbidden transitions in a graph. Matematickỳ časopis 18(1), 76–80 (1968)

    MathSciNet  MATH  Google Scholar 

  27. Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96(4), 514–528 (2006)

    Article  MathSciNet  Google Scholar 

  28. van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings, pp. 566–577 (2009)

Download references

Acknowledgements

The authors would like to thank the anonymous reviewer for pointing out the previous mistake on red–blue Eulerian trails for directed graphs and for indicating proper citations.

Author information

Authors and Affiliations

  1. University of Bergen, Bergen, Norway

    Benjamin Bergougnoux

  2. LIMOS, CNRS, Université Clermont Auvergne, Aubière, France

    Mamadou Moustapha Kanté

  3. Department of Mathematics, Incheon National University, Incheon, South Korea

    O-joung Kwon

  4. Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea

    O-joung Kwon

Authors
  1. Benjamin Bergougnoux
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mamadou Moustapha Kanté
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. O-joung Kwon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to O-joung Kwon.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An extended abstract appeared in Algorithms and Data Structures, WADS 2017 [3]. B. Bergougnoux and M.M. Kanté are supported by French Agency for Research under the GraphEN Project (ANR-15-CE40-0009). O. Kwon is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (ERC consolidator grant DISTRUCT, Agreement No. 648527), also supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294), and also supported by Institute for Basic Sciences (IBS-R029-C1).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bergougnoux, B., Kanté, M.M. & Kwon, Oj. An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width. Algorithmica 82, 1654–1674 (2020). https://doi.org/10.1007/s00453-019-00663-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-019-00663-9

Keywords

Search

Navigation