New answers tagged hamiltonian-path
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