New answers tagged

1

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


Top 50 recent answers are included