4

The complete digraph of $n$ nodes, $K_n$ has $n(n-1)$ edges. Describe a digraph of $n$ nodes with $n(n-1)-\delta$ edges as a digraph "with $\delta$ edges removed". A proof by induction The following is an outline to prove by induction that every digraph of $n$ nodes with $n-2$ edges removed contains a Hamiltonian cycle. The base case, when $n=2$ or ...


3

TSPLIB contains some instances of Hamiltonian Cycle. Haythorpe [1] proposes a set of around a thousand instances which are claimed to be "structurally difficult" (not necessarily large). Haythorpe, Michael. "FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem." arXiv preprint arXiv:1902....


3

You probably haven't found anything in your searches because this problem is fairly easy to solve, without needing any fancy methods. If the graph is strongly connected, then it is easy. Let $s$ be the starting node. Pick any vertex $v$ you haven't visited yet, and append a path $s \leadsto v$ followed by some path $v \leadsto s$ (both must exist, since ...


2

1. if P=NP does each of the problems on the left reduce to the easy problem (in P) in its immediate right? If P=NP then every problem on the left is in P, and trivially polynomially equivalent to every problem on the right. There is no special formal correspondence between the pairs of problems in each row of the table. The authors probably chose informally ...


2

No. There has to be a way to verify that your choices led to a correct choice, in polynomial time (with an ordinary deterministic computer). Given a particular Hamiltonian path, there's no way to verify it is the least Hamiltonian path (in polynomial time). The "space alien" stuff is just intuition, but if you want to know what it means in a ...


2

Your definition: A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of G exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated 2 or even more times). I'll call this revisited vertex (for a given $C$) the nexus of $C$ and look at a case that shows that even if we know which ...


2

Yes, any constant is a polynomial of degree zero.


2

I think what you're looking for, like I was, is the Minimum Spanning Tree. Here is an article about it.


2

If you are allowed to visit vertices more than once, many graph theorists use the term walk instead of path, i.e., a path is a walk where each vertex is visited only once (others use the pair path and simple path for walk and path). The shortest walk visiting every vertex may be called a Hamiltonian walk (see MathWorld), although this notion is not nearly as ...


2

If you choose a Hamiltonian cycle at random, the expected number of edges missing is strictly less than $1$.


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


1

You just need to add $n$ (where $n$ is the order of the graph) vertices with no additional edges.


1

First the reduction from P2 to P1 is easy cause if you can decide whether there is one cycle you can also decide whether there is at least one cycle. The other way around is more tricky. Notice that P1 can be solved in polynomial time if we have an oracle for P2 (an oracle for P2 means that we can use a subroutine that solves P2). algorithm for P1 with input ...


1

Let's call two vertices $u$ and $v$ comparable if there is an oriented path from $u$ to $v$ or from $v$ to $u$, and call them incomparable otherwise. Now let's prove that if there is no Hamiltonian path in DAG then there exist two incomparable vertices. Let's use a proof by contradiction and prove instead that if all vertices in a given DAG are pairwise ...


Only top voted, non community-wiki answers of a minimum length are eligible