Title: An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width,
Abstract: 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 naive algorithm that runs in time
$n^{\mathcal{O}(k^2)}$ by Espelage et al. (WG 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)}$ (SIAM. J.
Computing 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.