# Questions tagged [hamiltonian-circuit]

The tag has no usage guidance.

32 questions
Filter by
Sorted by
Tagged with
26 views

### optimal hamiltonian cycle in the Nearest Neighbor algorithm for the Traveling Salesman Problem

how to prove that in the Nearest Neighbor algorithm for the Traveling Salesman Problem with one modification, if it finds a hamiltonian cycle, it's the optimal cycle. the modification is if the ...
26 views

### Hamiltonian Graph Way

Recently i studied three theorems which says about Hamiltonian graph, they are as follows, Dirac's Theorem: Let G be some simple graph of order n >= 3, for all vertices of the graph G, its degree ...
24 views

### Why HC-k-regular-(n-even) being NP-Complete implies HC-k-regular is NP complete?

In , Corollary 2.3, after proving that HC-k-(n-even) for a fixed k >= 3, the paper says that HC-k-regular being NP Complete is an inmediate consequence of the former. Where: HC-k-regular-(n-even)...
237 views

### Finding a Hamiltonian Cycle in a directed graph - graph problem

$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
163 views

### $k$-Opt TSP Local Search is exact when $k = |V| - 1$

I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP). We'll ...
175 views

### $k$-Opt TSP Local Search is NOT exact when $k = \lceil |V|/2 \rceil$

I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP). We'll ...
42 views

### Difficulty in finding a counter example for a polynomial reduction

I am doing some exercises on proving NP Complete problems and the first problem was directed bipartite graphs with a Hamiltonian cycle and the second one was undirected bipartite graphs with a ...
151 views

### Hamiltonian cycle in $C_n^k$ in polynomial time for constant $k$?

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

### prove that Integer partition problem is NP complete using Hamiltonian Cycle

Show that Integer parition problem is NP-complete using the fact that Hamiltonian cycle is NP-Complete My Thoughts : Integer paritition problem is about partitioning a given set of integers into two ...
672 views

### Proving NP-hardness of Hamiltonian Cycle problem variant

I need to prove that determining whether a graph has a relaxed-Hamiltonian cycle (definition given ahead) is NP-hard. A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex ...
1 vote
44 views

### Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant. I saw the question below on an old stack exchange question when looking to ...
84 views

4k views

### Find hamilton cycle in a directed graph reduced to sat problem

I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to ...
271 views

### How many inputs does the Hadamard gate have?

Look at the diagram in the middle of page 6-3 here, http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf I am confused as to how should one think ...
211 views

### Upper bound on the number of hamiltonian cycles on a $n \times n$ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n$ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$. Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$. For ...