3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @InuyashaYagami done (They are vertices, and $ij$ represents an edge) $\endgroup$ Aug 29 at 5:50
  • 1
    $\begingroup$ @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 $\endgroup$ Aug 29 at 5:54
  • 1
    $\begingroup$ @InuyashaYagami Yes exactly, thank you $\endgroup$ Aug 29 at 5:59
  • $\begingroup$ Is the algorithm of the form $O(n^k)$ allowed? $\endgroup$ Aug 29 at 6:08
  • $\begingroup$ @InuyashaYagami Yes, I am looking for something polynomial time in $n$ and constant $k$, so it would work $\endgroup$ Aug 29 at 6:23
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Without $k$ dependency, the problem is NP-hard. $\endgroup$ Sep 2 at 4:47
  • $\begingroup$ I have added an answer. Please check if it makes sense. $\endgroup$ Sep 2 at 4:55
  • $\begingroup$ 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. $\endgroup$ Sep 2 at 9:24
  • $\begingroup$ 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)$. $\endgroup$ Sep 2 at 9:42
  • $\begingroup$ @EmilJeřábek Thanks, I am new to studying FPT, so I didn't know that trees can be found in FPT linear time! $\endgroup$ Sep 4 at 4:42
1
$\begingroup$

Addressing another question of OP:

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

$\endgroup$
3
  • $\begingroup$ As specified in the question, $k$ is a constant. $\endgroup$ Sep 2 at 6:59
  • $\begingroup$ @EmilJeřábek Yeah, you are right. That I know. I was addressing this question of OP. $\endgroup$ Sep 2 at 7:04
  • $\begingroup$ 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. $\endgroup$ Sep 2 at 8:41

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.