An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width

Benjamin Bergougnoux, Mamadou Moustapha Kanté, O-joung Kwon

In this paper, we prove that, given a clique-width $k$-expression of an $n$-vertex graph, \textsc{Hamiltonian Cycle} can be solved in time $n^{\mathcal{O}(k)}$. This improves the n…