Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
58 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 ...
shh's user avatar
  • 35
0 votes
1 answer
15 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 ...
Maceo Cardinale Kwik's user avatar
0 votes
0 answers
11 views

Are there any good papers that provide good definitions for the Minimum Weight Hamiltonian Path Problem?

I am looking for a paper to cite in a paper of my own regarding the Minimum Weight Hamiltonian Path Problem. This is distinct from the TSP because it is a path, not a cycle, meaning that a return to ...
Darcy Sutton's user avatar
1 vote
0 answers
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 ...
BSE10's user avatar
  • 11
0 votes
0 answers
19 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 ...
uzu's user avatar
  • 1
0 votes
1 answer
242 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
2 votes
1 answer
79 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 ...
Tortar's user avatar
  • 167
3 votes
2 answers
151 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
3 votes
0 answers
119 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 ...
Edgar's user avatar
  • 31
3 votes
2 answers
228 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)$ ...
Amal Sailendran's user avatar
0 votes
2 answers
364 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, ...
pekusbill's user avatar
1 vote
1 answer
84 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 ...
Anonymous's user avatar
1 vote
1 answer
175 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 ...
daniel's user avatar
  • 11
3 votes
3 answers
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 ...
maplemaple's user avatar
0 votes
1 answer
547 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 ...
heretoinfinity's user avatar
1 vote
1 answer
72 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 ...
Jesus is Lord's user avatar
2 votes
2 answers
705 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
0 votes
0 answers
340 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, ...
heretoinfinity's user avatar
0 votes
1 answer
320 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, ...
heretoinfinity's user avatar
0 votes
0 answers
66 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 ...
K.N's user avatar
  • 101
1 vote
1 answer
516 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 ...
Aviv Liberman's user avatar
2 votes
1 answer
130 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
1 vote
1 answer
349 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 ...
Adam Tolnay's user avatar
0 votes
2 answers
1k 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
3 votes
1 answer
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?
Hicham ATATRI's user avatar
2 votes
1 answer
275 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 ...
Baksel's user avatar
  • 143
3 votes
2 answers
87 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 ...
snowfrogdev's user avatar
1 vote
1 answer
802 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 ...
asv's user avatar
  • 345
3 votes
3 answers
409 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 ...
Alexander's user avatar
1 vote
1 answer
91 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 ...
TomR's user avatar
  • 1,381
2 votes
1 answer
890 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 ...
TomR's user avatar
  • 1,381
3 votes
2 answers
92 views

Finding a Hamiltonian path in this graph family

Given a directed graph $G = (V, E)$, you have been told that a Hamiltonian path $p_0p_1\ldots p_V$ exists with the property that for each edge $p_ip_j$ that is not part of the Hamiltonian path, $i >...
KKOrange's user avatar
  • 131
4 votes
1 answer
1k views

Minimum Path cover in a Directed Acyclic Graph

Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-...
Farah Mind's user avatar
0 votes
0 answers
52 views

Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
inaderi's user avatar
  • 13
1 vote
1 answer
157 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 ...
inaderi's user avatar
  • 13
0 votes
1 answer
106 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 ...
Swanny's user avatar
  • 1
2 votes
1 answer
54 views

Shortest hamiltonian path for different dimension points

The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$. For example if for $k=1$, the shortest Hamiltonian path will be the sorted ...
Vikas Shetty's user avatar
2 votes
0 answers
104 views

Comparing locally maximal and localy minimal Hamiltonian paths [closed]

Let $K_n$ be a weighted complete graph on $n$ vertices. Two Hamiltonian paths are formed as follows. The first one, $H$, is formed by starting at an arbitrary vertex, and at each stage proceeding from ...
arielb's user avatar
  • 19
1 vote
3 answers
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 ...
Abhijit Sarkar's user avatar
5 votes
1 answer
239 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 ...
idoby's user avatar
  • 151
2 votes
2 answers
1k views

Is the longest Hamiltonian cycle NP-complete?

As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing ...
John Slaine's user avatar
2 votes
1 answer
463 views

Proving that Hamiltonian Cycle is reducible to a travelling problem?

I chanced upon the following question online: A company has two trucks, and must deliver a number of parcels to a number of addresses. They want both drivers to be home at the end of the day. ...
Carrein's user avatar
  • 121
1 vote
2 answers
388 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
87 views

Can this Arrow-Ring puzzle be encoded as an integer programming problem?

I would like to write a solver for these kind of Arrow-Ring puzzles. However, I can't encode all the constraints correctly. I noticed that Sudoku can be solved using integer programming and I am ...
john mangual's user avatar
  • 1,931
1 vote
0 answers
563 views

Minimum weight Hamiltonian path on a weighted (0 and 1) tournament graph

Suppose we have a weighted tournament graph. (A directed graph in which every pair of distinct vertices is connected by a single directed edge.) The weights are constrained to be 0 and 1. I know ...
Vinayak Suresh's user avatar
3 votes
1 answer
6k views

Detecting Hamiltonian path in a graph

There are various methods to detect hamiltonian path in a graph. Brute force approach. i.e. considering all permutations T(n)=O(n*n!) Backtracking T(n)=O(n!) Using Dynamic programming T(n)=O(2^n * n^...
shiwang's user avatar
  • 481
0 votes
1 answer
817 views

DAG Hamiltonian Path NP-complete

The book computers and Intractability mentions that Hamiltonian Path problem is not NP-complete in DAG. But if Hamiltonian Cycle is NP-complete in digraph then I can split a vertex and create two ...
Neel Basu's user avatar
  • 141
1 vote
1 answer
2k 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 ...
Khan Saab's user avatar
  • 253
4 votes
3 answers
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 ...
Ron Inbar's user avatar
  • 153
2 votes
1 answer
308 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,408