Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

Question

We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover.

Let $G$ be connected simple graph.

$k$-clique cover of graph $G$ is partition of the vertices of $G$ into $k$ disjoint cliques $D'_i$.

1. Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle in time $O(\mathrm{polynomial}(n) n^{O(k)}$) or better?
2. Let $k$ be fixed, is it true that for all graphs with given $k$-clique cover Hamiltonian cycle is polynomial in $n$?

The basic idea is that all paths in cliques are easy.

One possible approach is to merge the cliques to single vertex and then enumerate walks allowing visiting vertex more than once.

For $k=2$ the answer is easily true.

For $k=3$ the merged graph is either $K_3$ or $P_3$ and we can try to extend walk to Hamiltonian cycle in $G$.

For $k=4$ the merged graph might be claw, so we need more complicated algorithm.

Answer 1

Yes, this problem is FPT. We showed this in the paper "Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018).

In particular, in this paper we state the result for Hamiltonian Path, but things doesn't change much if you want to consider Hamiltonian Cycle. In the conference version (and the slightly outdated version on the arxiv) we state the result as parameterizing by the chromatic number of the complement of the input graph (which is equal to clique cover).