# Questions tagged [hamiltonian-circuit]

The tag has no usage guidance.

34 questions
Filter by
Sorted by
Tagged with
21 views

### Limited constant degree HamCycle

Let $G=(V,E)$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem. In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges ...
• 465
351 views

### Is determining the existence of a Hamiltonian cycle in a chordal graph NP-hard?

The Hamiltonian cycle problem asks if a given graph contains a Hamiltonian cycle. The Hamiltonian cycle problem belongs to the class of NP-complete problems. However, for some special classes of ...
• 417
39 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 ...
• 45
35 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 ...
25 views

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

In [1], 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)...
• 103
292 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 ...
• 71
216 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 ...
238 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 ...
43 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 ...
155 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 ...
• 613
1 vote
124 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 ...
888 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
45 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 ...
113 views

• 473
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 ...
301 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 ...
• 1,145
216 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 ...
• 161
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 ...