Questions tagged [hamiltonian-circuit]
The hamiltonian-circuit tag has no usage guidance.
32
questions
0
votes
1
answer
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 ...
- 35
-1
votes
1
answer
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 ...
0
votes
1
answer
24
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
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 ...
- 71
3
votes
1
answer
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 ...
- 235
4
votes
1
answer
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 ...
- 235
0
votes
0
answers
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 ...
- 1
3
votes
2
answers
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 ...
- 593
0
votes
0
answers
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 ...
- 49
2
votes
2
answers
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
1
answer
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 ...
0
votes
1
answer
84
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 ...
- 137
2
votes
1
answer
130
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
1k
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
139
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
217
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
731
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
164
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
182
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
563
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
388
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
308
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,408
3
votes
1
answer
252
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,184
1
vote
1
answer
391
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
566
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
824
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 $\...
- 463
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
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 ...
- 1,125
6
votes
0
answers
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 ...
- 151
0
votes
1
answer
677
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
161
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,256