# Tag Info

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\... 1 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$... 0 Let$G$be a DAG with$G = (V, E)$. Recall that every DAG has at least one topological ordering. Assume$G$is Hamiltonian, i.e. there exists a path of length$|V|$, e.g.$p = [v_1, \ldots, v_n]$where$n = |V|$. Note that there's a path from$v_i$to$v_j$whenever$i < j$. Thus$p$is a topological ordering: if there is any edge from$v_j$to$v_i\$ with ...