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$.
- Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle in time $O(\mathrm{polynomial}(n) n^{O(k)}$) or better?
- 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.