# Questions tagged [hamiltonian-path]

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

72 questions
Filter by
Sorted by
Tagged with
58 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 ...
37 views

### Diameter of a disconnected graph

Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?
110 views

### What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?

I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the ...
19 views

### Does this imply Hamiltonian path cannot be decided in nondeterministic logspace?

Suppose I nondeterministically walk around in a graph with n vertices. When looking for a Hamiltonian path, at some point I’ve walked n/2 vertices. There are (n choose n/2) different combinations of ...
33 views

### Does this imply checking a candidate Hamiltonian Path solution can be done in logspace?

Assume vertices are integers base 2. Smallest vertex is 1. There are n vertices. Our input is: the number of vertices (n expressed in log(n) bits - ...
42 views

### Finding a hamiltonianISH path in a graph

Problem statement Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions. Given any starting node. What ...
141 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 ...
164 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 ...
27 views

### How can I convert this graph into CNF to solve the hamiltonian path with SAT?

So I have this graph, I am following the rules outlined in these slides: https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20111018.pdf The rules for converting the graph to CNF and the proof are in ...
22 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 ...
135 views

### Does topological sort exist for any complete directed acyclic graph?

Let's assume that DAG is complete: there is directed edge among every to nodes. Does topological sort of vertices exist for any such graph? I.e. is it possible to make linear list of nodes in which ...
62 views

73 views

### How a NTM guessing depends on the input?

After looking at the definition of nondeterministic TMs, it seems that, while guessing, the machine could go to at most $|Q|\times | \Gamma |$ configurations, being in a particular one. However, if ...
3k views

### Hamiltonian path in directed graph

Let G be a directed graph such that every two vertices are connected by a single edge. How do I proof that such G has an hamiltonian path?
130 views

### Solving Hidoku problem using reduction to Hamilton path

It seems like people have discussed this reduction here: Is Hidoku NP complete? But it looks like the solution that was given only tells you if the Hidoku problem has a solution or not (if an ...
2k views

### Prove that a hamiltonian DAG has a single topological sort

I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort". This is pretty much the idea of what I've come along: lets prove by ...
184 views

### Is the search for a k-Hamiltonian Path NP-hard?

A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors. ...
278 views

### Number of “hamiltonian tours” from upper left to lower left corner of a grid graph?

I got the following as an interview question: Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the ...
2k 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 ...
262 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 ...
606 views

### NP-completeness of the exact distance problem

I am currently learning about NP-complete problems and I want to make sure my understanding is correct. Here is a problem I am working on currently: The exact distance problem is, given an edge-...
988 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....
654 views

### Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ...
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 ...
2k views

### Poly-time reduction from directed Hamiltonian Path to undirected HP, both with with known start and end

this is homework, so PLEASE do not give me the solution(!), but help me get there on my own. I've got to proof that directed Hamilton Path with fixed stard and ending and undirected Hamilton Path ...
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 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 ...
349 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 ...