Questions tagged [hamiltonian-circuit]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
31 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 ...
2
votes
2answers
93 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
1answer
33 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 ...
-1
votes
1answer
26 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 ...
2
votes
1answer
38 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 ...
0
votes
2answers
133 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 ...
2
votes
1answer
97 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 ...
1
vote
1answer
210 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
1answer
212 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 ...
4
votes
0answers
131 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 ...
1
vote
1answer
139 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 ...
3
votes
2answers
296 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
2answers
339 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 ...
2
votes
1answer
192 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 ...
3
votes
1answer
173 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 ...
1
vote
1answer
296 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 ...
1
vote
0answers
466 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 ...
4
votes
2answers
639 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$...
0
votes
1answer
2k 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 $\...
4
votes
2answers
3k 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 ...
3
votes
1answer
154 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 ...
5
votes
0answers
187 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 ...
0
votes
1answer
562 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
1answer
138 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 ...