Questions tagged [hamiltonian-circuit]
The hamiltonian-circuit tag has no usage guidance.
35
questions
-1
votes
1
answer
49
views
Prove that 3COLORHC is NP-complete using Hamiltonian Cycle
We know that the language of undirected graphs that contain a Hamiltonian cycle is NP-complete
we need to use this to prove that the following language is NP-complete (I know how to prove that it is ...
- 117
2
votes
1
answer
28
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 ...
- 485
3
votes
1
answer
357
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
0
votes
1
answer
41
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 ...
- 67
0
votes
1
answer
37
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 ...
- 19
0
votes
1
answer
26
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
0
votes
1
answer
293
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
3
votes
1
answer
226
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 ...
- 235
4
votes
1
answer
248
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 ...
- 235
0
votes
0
answers
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 ...
- 1
3
votes
2
answers
156
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 ...
- 623
1
vote
0
answers
125
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 ...
- 59
2
votes
2
answers
930
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
1
answer
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 ...
0
votes
1
answer
114
views
NP-complete problem of partitioning into several sets with a Hamiltonian cycle
How to prove the $NP$-completeness of the language $L$ = $\{$$(G, k)$: the vertices of an undirected graph $G$ can be partitioned into $k$ pairwise disjoint sets of pairwise different sizes so,
that ...
- 147
2
votes
1
answer
162
views
Examples of difficult Hamiltonian Cycle Problems
I am working on implementing algorithms to solve Hamiltonian Cycle Problem. I need difficult problem graphs to test my implementations but my google-fu is weak and am unable to find any.
Please advise ...
- 25
0
votes
2
answers
2k
views
Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle
The following is an excerpt from a material on NP-Theory:
"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a
path from s to t using edges of G, on which ...
- 52
2
votes
1
answer
141
views
HamiltonianCycles in Random Graphs
Lets say we consider the Erdős-Renyi undirected random graph $G(n,p)$ with $V(G) = \{1,2,\cdots,n\}$ and $\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V $.
Is there anything we can say ...
- 217
1
vote
1
answer
218
views
Hamilton Circuit
The Dirac's theorem states that:
"For a Graph G with N vertices, if the degree of each vertex is atleast N/2 then, the Graph has a Hamilton Circuit."
Can the same be said if a graph has a Hamilton ...
2
votes
1
answer
927
views
Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G
In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:
Suppose that a friend tells you that a given
graph G is hamiltonian, and then offers to prove it by giving ...
- 229
4
votes
0
answers
170
views
Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?
I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows.
We have a directed graph and each node can have at most 3 outgoing edges. Determine if this ...
- 49
1
vote
1
answer
195
views
Find Hamiltonian cycle in polynomial time
I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only ...
- 123
3
votes
2
answers
611
views
What is the best way to merge cycles to minimise total weight?
Suppose I have a vertex-disjoint set $S$ of simple cycles in a weighted undirected graph. So no vertex $v$ is contained in more than one cycle. A cycle $c$ is a closed path with no repeated vertices: $...
1
vote
2
answers
393
views
Solve Hamilton Circuit with Hamilton Path
I want to show the reduction $HC \leq HP$.
Let $G=(V,E)$ be my undirected graph.
My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\{e\})$ has a Hamiltonian Path. If this is true ...
- 113
2
votes
1
answer
347
views
Find the $k$-th lexicographically smallest hamiltonian circuit
Let's say we have given unweighted directed graph with $N$ nodes and $M$ edges, and we want to find the $K$-th hamiltonian circuit, ordered in lexicographical order.
For example, if we have complete ...
- 1,428
3
votes
1
answer
257
views
Complexity of ANOTHER HAMILTONIAN CIRCUIT problem
All references I find about the ANOTHER HAMILTONIAN CIRCUIT problem:
Given a graph and a hamiltonian circuit on it, is there another
hamiltonian circuit on it?
I was trying to reduce it to the ...
- 2,204
1
vote
1
answer
397
views
NP-Hardness of Hamiltonian cycle with $|V|$ divisible by 3
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Are ...
- 61
1
vote
0
answers
576
views
Find reduction from Hamiltonian Cycle to Double Hamiltonian Cycle
$$DoubleHC=\{G\,| \text{G has at least two Hamiltonian Cycles}\}$$
I think about take a graph with HC and add to it two vertexes and edges to two randomally vertexes, but without success. Is my try ...
- 121
4
votes
2
answers
870
views
An FPT algorithm for Hamiltonian cycle running parameterized by treewidth
I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $\text{tw}(G)^{O(\text{tw}(G))} \cdot n$...
- 61
0
votes
1
answer
3k
views
A version of the longest simple cycle problem - NP-completeness reduction proof
I've been learning about proving NP-completeness via reduction, and came across the following problem:
Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using $\...
- 473
5
votes
3
answers
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 ...
- 53
3
votes
1
answer
303
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,155
6
votes
0
answers
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
0
votes
1
answer
683
views
Multiple of Hamiltonian Cycles
I'm currently confused whether a graph should contain strictly one distinct Hamiltonian Cycle. (given that [1,2,3,4,1] and [2,3,4,1,2] are the same).
I was wondering if, by definition, there can be ...
5
votes
1
answer
166
views
Hamiltonian circuit for a family of graphs
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 ...
- 3,276