1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Laakeri
    Jan 21, 2020 at 17:15
  • $\begingroup$ @Laakeri I am also interested in answer O(polynomial(n) n^f(k)) for polynomial f. $\endgroup$
    – joro
    Jan 21, 2020 at 17:41
  • 1
    $\begingroup$ Cross-posted to mathoverflow.net/q/350798 . $\endgroup$ Jan 22, 2020 at 14:24

1 Answer 1

6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.