# Hamiltonian cycle in $C_n^k$ in polynomial time for constant $k$?

Let $$C_n$$ denote the cycle graph over $$n$$ vertices. Let $$C_n^k$$ denote the $$k$$-th power of the cycle graph, or namely that for two vertices $$i,j$$, $$(i,j)\in Edges(C_n^k) \iff |i-j|\leq k$$ for a constant $$k$$.

Now given a subgraph $$G$$ of $$C_n^k$$, how can we find a hamiltonian cycle (if it exists) in $$G$$ in polynomial time (in $$n$$)?

I've tried solving this with DP but the best I've reached is $$O(2^nn)$$ which just matches the known DP for hamiltonian cycle. I would prefer hints over full answers.

• @InuyashaYagami done (They are vertices, and $ij$ represents an edge) Aug 29, 2021 at 5:50
• @InuyashaYagami $C_n$ is a cycle with vertices $1,2,...,n$. $C_n^k$ is a graph with vertices $1,2,...,n$ and edges $(i,i-k \mod n), (i, i-k+1 \mod n), ..., (i, i-1), (i, i+1 \mod n), ..., (i, i+k \mod n)$ for all i Aug 29, 2021 at 5:54
• @InuyashaYagami Yes exactly, thank you Aug 29, 2021 at 5:59
• Is the algorithm of the form $O(n^k)$ allowed? Aug 29, 2021 at 6:08
• @InuyashaYagami Yes, I am looking for something polynomial time in $n$ and constant $k$, so it would work Aug 29, 2021 at 6:23

Here is an overkill solution:

Lemma: The subgraph $$G$$ has tree-width at most $$2k$$.

Proof. Treat all additions and subtractions in what follows in circular modulo arithmetic (for example $$n+1 = 1$$). Also assume $$n\gg k$$. Let $$L_j=\{j-1, j-2, ..., j-2k\}$$ and $$R_j=\{j+1, ..., j+2k\}$$. Then the path decomposition for $$C_n^k$$ of $$(L_1\cup \{1\}\cup R_1), (L_1\cup \{2\} \cup R_2), (L_1\cup\{3\}\cup R_3), ...$$ is a path (tree) decomposition with width $$2k$$, and so the tree-width of $$C_n^k$$ is at most $$2k$$ so a subgraph of $$C_n^k$$ has tree-width at most $$2k$$.

Since the tree-width of $$G$$ is at most $$2k$$, then there is a $$O(n^{O(k)})$$ algorithm that finds a nice tree decomposition $$T$$ for $$G$$. We can then run the FPT hamiltonian cycle algorithm on $$T$$ to find a hamiltonian cycle for $$G$$ in $$O(k^{O(k)}n)$$ time.

Overall, the algorithm takes $$O(n^{O(k)})$$, which is polynomial time. I would still be interested in a polynomial time solution without a $$k$$ dependency, or even with dependency $$k$$ but simpler.

• Without $k$ dependency, the problem is NP-hard. Sep 2, 2021 at 4:47
• I have added an answer. Please check if it makes sense. Sep 2, 2021 at 4:55
• I’m not sure where you got the $n^{O(k)}$ dependency. Tree decomposition can be found in FPT time linear in $n$. And anyway, Courcelle’s theorem directly says that Hamiltonian cycle, which is an $\mathrm{MSO}_2$ property, is solvable in time $O(f(k)n)$ on graphs of treewidth $\le k$, without assuming that it is presented with a tree decomposition. Sep 2, 2021 at 9:24
• Strictly speaking, Coucelle’s theorem applies to decision problems rather then search problems. But anyway, we can construct a Hamiltonian path by binary search using $n$ queries of the form “can a given path in $G$ be completed to a Hamiltonian cycle”, which are FPT linear in $n$; thus, the whole algorithm takes time $O(f(k)n^2)$. Sep 2, 2021 at 9:42
• @EmilJeřábek Thanks, I am new to studying FPT, so I didn't know that trees can be found in FPT linear time! Sep 4, 2021 at 4:42

Suppose $$k$$ is equal to $$n$$. If so, then $$C_{n}^{k}$$ would be a complete graph. And, suppose if we could check if a Hamiltonian cycle exists in any subgraph $$G$$ of $$C_n^{k}$$ in polynomial time (i.e., $$poly(n,k)$$), then it would mean that we can solve Hamiltonian Cycle problem in polynomial time on any graph with $$n$$ vertices.
Since the Hamiltonian Cycle problem is $$\mathsf{NP}$$-hard; therefore, the stated problem is also $$\mathsf{NP}$$-hard. In other words, it is hard to find a Hamiltonian cycle in $$G$$ in time polynomial in $$k$$ and $$n$$.
• As specified in the question, $k$ is a constant. Sep 2, 2021 at 6:59
• I see. You should have made it clear that you are not answering the original question. Even so, I'm pretty sure the OP knows that Hamiltonian cycle is NP-complete. While the formulation in their answer is not quite clear, I believe that what they are asking is if the problem can be solved in time where the dependency on $k$ cannot appear in the exponent: $f(k)n^{c}$ for some constant $c$ and a function $f$. Iow, if Ham Cycle is fixed-parameter tractable with $k$ being the parameter. Your answer does not address that. Sep 2, 2021 at 8:41