# Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

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.

• If there is some bound $f(k)$ for the number of times the path in a yes-instance moves from a clique to another, then you can obtain an FPT algorithm with color coding and dynamic programming. Jan 21, 2020 at 17:15
• @Laakeri I am also interested in answer O(polynomial(n) n^f(k)) for polynomial f.
– joro
Jan 21, 2020 at 17:41
• Cross-posted to mathoverflow.net/q/350798 . Jan 22, 2020 at 14:24