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.

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

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Without $k$ dependency, the problem is NP-hard. $\endgroup$
    – Inuyasha Yagami
    Sep 2, 2021 at 4:47
  • $\begingroup$ I have added an answer. Please check if it makes sense. $\endgroup$
    – Inuyasha Yagami
    Sep 2, 2021 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$
    – Emil Jeřábek
    Sep 2, 2021 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$
    – Emil Jeřábek
    Sep 2, 2021 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$
    – AspiringMat
    Sep 4, 2021 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$.

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

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.