1
$\begingroup$

Let $G$ be connected simple graph.

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)}$)?
  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.

Small cliques need not be on the merged walk, which complicates the algorithm.

$\endgroup$
  • 1
    $\begingroup$ Cross-posted to cstheory.stackexchange.com/q/46218 , and to make things worse, with no cross-links from one post to the other. You’ve been here for many years, so you are well aware that this is unacceptable and rude behaviour. $\endgroup$ – Emil Jeřábek Jan 22 at 14:23
2
$\begingroup$

It's FPT. The idea is that one never needs to move between different cliques too many times.

Lemma If there is a hamiltonian cycle, then there is a hamiltonian cycle which, for all $i\neq j\in\{1,\dots,k\}$, uses at most one edge from $D_i$ to $D_j$.

Proof Consider a hamiltonian cycle which minimizes the number of edges between different cliques. Suppose it uses some edges from $D_i$ to $D_j$ twice, for some $i,j$. That is, the sequence of vertices is of the form $P a_1 b_1 Q a_2 b_2 R$, where $a_1,a_2 \in D_i$, $b_1,b_2 \in D_j$ and $P,Q,R$ are whatever, possibly empty. Then (assuming the graph is undirected) you can "flip the square" to get the hamiltonian cycle $P a_1 a_2 Q^{-1} b_1 b_2 R$. But this uses two non-clique edges less (by adding in-clique edges $a_1 a_2$ and $b_1 b_2$ instead). $\square$

So in particular there is a hamiltonian cycle that enters and leaves each clique $D_i$ at most $2k$ times (it might need to go from $D_i$ to $D_j$ and then back). This already gives an easy $n^{O(k^2)}$ algorithm: guess the sequence of movements between cliques (that is, try all sequences of clique names of length at most $k^2$) and for each step in the sequence guess which vertex you leave from and which you enter into. Then, for each such guess, it's trivial to check if that sequence can be extended with walks inside cliques to cover all vertices.

To get an FPT algorithm you can e.g. kernelize, i.e. remove things that are redundant, in a sense. Look at the bipartite graph between $D_i$ and $D_j$. If there is any vertex $v \in D_i$ of degree $>2k$, then select any $2k$ incident edges $F$ and remove the rest; the supposed hamiltonian cycle can be easily changed to use edges in $F$ in place of the removed ones (because it enters and leaves the clique $D_j$ at most $2k$ times), so that doesn't change the answer.

After this, in the bipartite graph between $D_i$ and $D_j$, every vertex has bounded degree. Now take any maximal matching (e.g. obtain it greedily). If it has more than $4k$ edges, then select any subset $F$ of $4k$ edges and remove the rest between $D_i$ and $D_j$. As before you can easily argue this won't change the answer. After such a removal, the bipartite graph has a maximal matching of at most $4k$ edges, so their endpoints make a vertex cover of at most $8k$ vertices. Since they have bounded degree, the number of edges between $D_i$ and $D_j$ is bounded by $16k^2$. Repeat for all $i\neq j$; then the total number of non-clique edges is $\leq 16k^4$. Any vertex that is not incident to any non-clique edge can be removed without changing the answer, so you're left with a graph on $\leq 32 k^4$ vertices, which you can solve brutally in time factorial in that, so $2^{O(k^4 \log k)}$. The above kernelization itself is easily implemented in time $\mathrm{poly}(k) \cdot m$ (linear in the number of edges).

I guess with some technical effort $2^{O(k^2 \log k)} \cdot m$ or even $2^{O(k^2 \log k)} + \mathrm{poly}(k) \cdot m$ should be possible, but it's hard to say whether $2^{O(k)} \mathrm{poly}(n)$ or $n^{O(k)}$ is possible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. Don't you need at least TWO edges and vertices between cliques, e.g. for 2K_3 + two edges? $\endgroup$ – joro Jan 23 at 9:39
  • $\begingroup$ At most one from $D_i$ to $D_j$, at most one other from $D_j$ to $D_i$. "It might need to go from $D_i$ to $D_j$ and then back." Or did I miss another factor of 2 somewhere? $\endgroup$ – Marcin W Jan 23 at 10:09
  • $\begingroup$ I misread the definition of Lemma in the beginning. There is similar known result on cstheory: cstheory.stackexchange.com/questions/46218/… $\endgroup$ – joro Jan 23 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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