Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [hamiltonian-path]

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

95 questions
Filter by
Sorted by
Tagged with
1 vote
96 views

### Non-brute force algorithm for a Eulerian like path

I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one ...
1 vote
221 views

### Prove the following claim on Hamilton Path?

I am trying to prove the following claim: Given DAG graph, there is Hamilton path iff the following algorithm returns true: Do topologic sorting. Move on the graph's vertices one by one (from low to ...
42 views

### Find every Hamiltonian path through a 4x4 matrix starting from a given X,Y?

As part of programming a game, I'm trying to generate all the paths through an NxN matrix that touch every cell once without revisiting any, starting from (0,0). Considering the matrix as a graph, ...
1 vote
34 views

### Reduction from Hamiltonian path to Tripartite decision problem

I teach a fairly advanced algorithms class to high schoolers and I accidentally presented them with a bunk reduction from Hamiltonian path to the Tripartite graph decision problem. My attempt involved ...
35 views

### Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes

I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
258 views

### Shortest Hamiltonian Path in a Complete Graph

I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm ...
49 views

### HAMILTONIAN PATH AND SUBSETSUM

If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P? ...
97 views

### Visiting all nodes of a directed graph exactly once (not dfs)

Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should ...
4k 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 ...
1 vote
36 views

### Why does greedy approach of constructing De Bruijin Sequence work?

I have recently discovered a greedy algorithm to construct De Bruijin Sequence. The greedy approach (prefer-largest specifically) works like the following: Start with a sequence of all 0's of length ...
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 ...
20 views

### To Prove NP-Completeness [duplicate]

Given a Directed Graph G, and some subsets of vertices T1,T2,..Tn(These subset can intersect) , is there a path in this graph such that it is acyclic and contains exactly 3 vertices from each Ti. I'm ...
1 vote
826 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 ...
291 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 ...
895 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 ...
83 views

### Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?

Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the ...
2k 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 ...
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 ...
121 views

### Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work

I am looking for an algorithm to a problem that I encountered when working with 3D modeling: On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
1k views

### find a path to visit every node in graph not necessarily once

I meet a problem but when I google, there are all Hamiltonian Path Problem: How to find a path to visit every node in directed graph(not necessarily once)? This problem is different from Hamiltonian ...
234 views

### Is this graph Hamiltonian?

My case is a directed graph with $n$ nodes with $(n-1)^2+1$ edges. I have done the following till now. We know that the maximum number of edges for a directed graph $K_n$ on $n$ nodes is $n(n-1)$ ...
445 views

### How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem

Task: A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, ...
686 views

### If P = NP, do these NP-complete problems reduce to these specific easier versions?

I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al. Chapter 8 has the table below and I am wondering: if $P = NP$ does each of the problems on the left reduce ...
1 vote
78 views

### Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?

My understanding of non-deterministic algorithms is that they're "as lucky as you want". ...you can think of the algorithm as being able to make a guess at any point it wants, and a space ...
869 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 ...
434 views

### Is reduction from Rudrata/Hamiltonian path to Rudrata/Hamiltonian cycle O(1)?

I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
371 views

### Is O(1) considered polynomial time?

I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
78 views

### Number of Hamilton paths in graphs

I am trying to find a fast algorithm that can compute the number of hamiltonian paths in an undirected graph. I saw this on the web, but it sounds like this finds all hamiltonian paths starting from ...
1 vote
595 views

### If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts

I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal. Can you ...
148 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 ...
1 vote
384 views

### What is the polynomial time reduction between these two Hamiltonian cycle problems?

Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle. Problem 2: Given an undirected graph, decide whether or not the ...
2k 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

### 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 ...
1k views

### Diameter of a disconnected graph

Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?
286 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 ...
127 views

### Decomposition of a directed graph into Hamiltonian paths

I was wondering if anyone knew of an algorithm that when given a directed graph will split it up into separate Hamiltonian paths. I don't really mind about nodes that can't be added to a path but as ...
92 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 ...
1 vote
826 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 ...
460 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 ...
1 vote
101 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 ...
961 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 ...
93 views

1 vote
2k 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 ...