Skip to main content

Questions tagged [hamiltonian-circuit]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
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 ...
Eric_'s user avatar
  • 465
3 votes
1 answer
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 ...
licheng's user avatar
  • 417
0 votes
1 answer
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 ...
vhd's user avatar
  • 45
0 votes
1 answer
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 ...
Niraj Jain's user avatar
0 votes
1 answer
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)...
hhaamm's user avatar
  • 103
0 votes
1 answer
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 ...
PK96's user avatar
  • 71
3 votes
1 answer
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 ...
Fimpellizzeri's user avatar
4 votes
1 answer
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 ...
Fimpellizzeri's user avatar
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 ...
sari98's user avatar
  • 1
3 votes
2 answers
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 ...
AspiringMat's user avatar
1 vote
0 answers
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 ...
Amit wadhwa's user avatar
2 votes
2 answers
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 ...
Dhruv Deshmukh's user avatar
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 ...
Inspector gadget's user avatar
0 votes
1 answer
113 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 ...
Kapa's user avatar
  • 137
2 votes
1 answer
152 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 ...
gautam's user avatar
  • 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 ...
Puneet's user avatar
  • 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 ...
ramseysdream111's user avatar
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 ...
Shashwat Vaibhav's user avatar
2 votes
1 answer
911 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 ...
KGhatak's user avatar
  • 229
4 votes
0 answers
167 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 ...
Davis's user avatar
  • 49
1 vote
1 answer
194 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 ...
shakeel osmani's user avatar
3 votes
2 answers
606 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: $...
Dmitry Kamenetsky's user avatar
1 vote
2 answers
391 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 ...
BlobbyBob's user avatar
  • 113
2 votes
1 answer
340 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 ...
someone12321's user avatar
  • 1,428
3 votes
1 answer
256 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 ...
user1868607's user avatar
  • 2,194
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 ...
Rakesh K's user avatar
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 ...
Dubon's user avatar
  • 121
4 votes
2 answers
861 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$...
Vandalo's user avatar
  • 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 $\...
user3280193's user avatar
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 ...
Dor Cohen's user avatar
3 votes
1 answer
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 ...
user6818's user avatar
  • 1,145
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 ...
Gaganpreet's user avatar
0 votes
1 answer
682 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 ...
Kevin Lloyd Bernal's user avatar
5 votes
1 answer
165 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 ...
André Souza Lemos's user avatar