<p>Yes, this problem is FPT. We showed this in the paper <a href="https://www.sciencedirect.com/science/article/abs/pii/S0166218X17302354" rel="noreferrer">"Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018)</a>.</p>

<p>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).</p>

CC BY-SA 4.0
2020-01-21T19:19:06.273Z
2020-01-21T19:19:06.273Z
Michael Lampis
<p>We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given <span class="math-container">$k$</span>-clique cover.</p>

<p>Let <span class="math-container">$G$</span> be connected simple graph.</p>

<p><span class="math-container">$k$</span>-clique cover of graph <span class="math-container">$G$</span> is partition of the vertices of <span class="math-container">$G$</span>
into <span class="math-container">$k$</span> disjoint cliques <span class="math-container">$D'_i$</span>.</p>

<ol>
<li>Given <span class="math-container">$G$</span> and <span class="math-container">$k$</span>-clique cover, can we solve Hamiltonian cycle
in time <span class="math-container">$O(\mathrm{polynomial}(n) n^{O(k)}$</span>) or better?</li>
<li>Let <span class="math-container">$k$</span> be fixed, is it true that for all graphs with given <span class="math-container">$k$</span>-clique
cover Hamiltonian cycle is polynomial in <span class="math-container">$n$</span>?</li>
</ol>

<p>The basic idea is that all paths in cliques are easy.</p>

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

<p>For <span class="math-container">$k=2$</span> the answer is easily true.</p>

<p>For <span class="math-container">$k=3$</span> the merged graph is either <span class="math-container">$K_3$</span> or <span class="math-container">$P_3$</span>
and we can try to extend walk to Hamiltonian cycle in <span class="math-container">$G$</span>.</p>

<p>For <span class="math-container">$k=4$</span> the merged graph might be claw, so we need
more complicated algorithm.</p>

CC BY-SA 4.0
2020-01-21T17:15:37.203Z
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.
Laakeri
CC BY-SA 4.0
2020-01-21T17:41:07.880Z
@Laakeri I am also interested in answer O(polynomial(n) n^f(k)) for polynomial f.
joro
CC BY-SA 4.0
2020-01-22T14:24:08.120Z
Cross-posted to https://mathoverflow.net/q/350798 .
Emil Jeřábek
<cc.complexity-theory><graph-theory><graph-algorithms>
Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?
joro
# Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

(Asked by: username_0 on 2020-01-21)

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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: 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.  
> **username_0**: @Laakeri I am also interested in answer O(polynomial(n) n^f(k)) for polynomial f.  
> **username_2**: Cross-posted to https://mathoverflow.net/q/350798 .  

---

## 1 answers

### Answer by username_3 on 2020-01-21. Score: 6

Yes, this problem is FPT. We showed this in the paper ["Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018)](https://www.sciencedirect.com/science/article/abs/pii/S0166218X17302354).

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).


---

