# Questions tagged [hamiltonian-path]

Questions on Hamiltonian paths, that is, paths that visit each vertex exactly once in a graph.

67 questions
Filter by
Sorted by
Tagged with
342 views

### How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?

I'm stuck on problem 9.4 from The Nature of Computation which reads: Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
2k views

### Constructing a random Hamiltonian Cycle (Secret Santa)

I was programming a little Secret Santa tool for my extended family's gift exchange. We had a few constraints: No recipients within the immediate family Nobody should get who they got last year The ...
2k views

### Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

I'm a little stuck on this question, any help would be appreciated! Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is ...
6k views

### Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
1k views

### How to generate graphs with a Hamiltonian path?

I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can ...
2k views

### Find a simple path visiting all marked vertices

Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$. The problem is to find a simple path in $G$ that visits the maximum possible number of ...
125 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 ...
152 views

### Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs. I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle (path)...
108 views

### Why is Adleman's molecular algorithm for Hamiltonian Path linear?

In Adleman's 1994 paper (archived), he describes a method of manipulating DNA molecules in a lab that results in a solution to the Hamiltonian Path problem with high probability. He claims that "The ...
291 views

### Does the Bondy-Chvátal theorem have algorithmic applications beyond Ore's theorem?

I'm toying around with graph properties and I want to make some effort to check whether a given graph is Hamiltonian. I understand that the general problem is NP-complete, but I'm looking for simple ...
251 views

### Is Hamiltonian path NP-hard on graphs of diameter 2?

Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$). Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs? Perhaps some motivation is in place: the question ...
176 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 ...
2k 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 ...
818 views

### Rearranging strings so that the Hamming distance between them is 1

This is a question from CodeFights.com: Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at ...
131 views

### How to find a path that connects all the dots in the matrix?

I have a matrix that consists of 0, 1, 2. 0 - dot. 1 - block. 2 - start dot (initial position in the path). I have to create a path from the start dot, that connects all the dots in the matrix and ...
1k views

### Hamiltonian path in grid graph

Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that ...
794 views

### Almost Hamiltonian

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice. Is the problem of determining whether a graph is almost Hamiltonian NP-complete?
4k views

For my case I have starting point and several cities. I want the shortest route to visit all cities without returning starting point. I have read several TSP algorithm and all include the return a ...
867 views

### Path in directed, weighted, cyclic graph with total distance closest to D?

Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d. Output: A path between A and B with distance closest to d....
1k views

### Minimum Length Hamiltonian Path Pair in O(n^2) or better

A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to ...
56 views

240 views

### Proving DPATH is NP-complete by a reduction from HAMPATH

I have a language DPATH that I'm trying to complete is NP-complete. ...
334 views

### Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
616 views

### Hamiltonian path and minimum spanning tree

Suppose i have a graph and i want to find minimum-spanning-tree. As in imperative languages we have to take specific steps from everynode(example ,we use kruskal's algorithm or prim's algorithm) to ...
1k views

### How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]

I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem. Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
445 views

### A basic question about approximation algorithms for the Traveling Salesman Problem

Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be ...
34 views

### Hamiltonian cycle, verifying and finding

If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle? My attempt is to delete an edge ...
14 views

### How complete directed graph with n-vertices is connected to the n-dimensional simplex and its triangulation?

Answer https://stackoverflow.com/a/26151549/1375882 suggests that Sperner's lemma can be used to prove the existence of index for the search Hamiltonian path in complete directed graph. But Sperner's ...
28 views

### Hamiltonian non intersecting path in plane

$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we ...
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 ...
Define $A = \{<G,s,t> :G$ is un directed graph that has a Hamilton path from $s$ to $t\}$ $B = \{<G> :G$ is un directed graph that has a Hamilton path$\}$ I would like to show that \$...