Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hamiltonian-path]

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

2
votes
1answer
28 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 ...
2
votes
0answers
81 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 ...
1
vote
3answers
213 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 ...
5
votes
1answer
96 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 ...
0
votes
0answers
32 views

Hamilton path and Euler circuits in Cycle graph

Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?
1
vote
2answers
132 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 ...
2
votes
1answer
82 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. ...
1
vote
2answers
158 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
36 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 ...
1
vote
0answers
186 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 ...
2
votes
1answer
847 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^...
0
votes
1answer
342 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 ...
1
vote
1answer
330 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 ...
4
votes
2answers
767 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 ...
2
votes
1answer
116 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 ...
6
votes
0answers
273 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 ...
1
vote
1answer
131 views

Reducing one variant of Hamiltonian path to another

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 $...
1
vote
1answer
58 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 ...
2
votes
1answer
2k 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?
0
votes
1answer
113 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 ...
2
votes
0answers
1k 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 ...
2
votes
1answer
156 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. ...
3
votes
1answer
175 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 ...
3
votes
2answers
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 ...
1
vote
1answer
214 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 ...
0
votes
1answer
525 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-...
3
votes
3answers
778 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....
-2
votes
1answer
499 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 ...
1
vote
1answer
960 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 ...
1
vote
0answers
764 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 ...
5
votes
2answers
960 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 ...
3
votes
2answers
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 ...
5
votes
1answer
278 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 ...
3
votes
1answer
694 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?
3
votes
2answers
3k views

What TSP variant doesn't return to start point?

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 ...
3
votes
0answers
283 views

Finding partial traveling salesman path of specified length

For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial ...
5
votes
0answers
157 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 ...
5
votes
1answer
114 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 ...
3
votes
1answer
985 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 ...
-1
votes
1answer
1k views

C program - Visually display Graph and checking for Hamiltonian Paths? [closed]

I have a very large graph in my c program with a list of nodes and edges. I want to print out the visual representation of this. What is the best way to go about this? Additionally what's the best ...
2
votes
1answer
158 views

Lower bounding the minimum equivalent graph

The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$. The minimum equivalent graph $G' = (...
0
votes
2answers
348 views

Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$ [closed]

I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a ...
5
votes
2answers
5k 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 ...
6
votes
3answers
1k 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 ...
1
vote
1answer
749 views

find the shortest path between two nodes where the number of edges is minimal [closed]

Say you are given an undirected unweighted graph, where s and t are nodes from the graph. d(s,t) means the distance between s and t which outputs the number of edges. How do I find the the maximum ...
1
vote
2answers
418 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 ...
5
votes
1answer
139 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)...
1
vote
1answer
2k views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
0
votes
0answers
56 views

A polynomial reduction from HAMPATH to LONG-PATH [duplicate]

$\text{HAMPATH} = \{(G=(V,E),s',t')| \text{ G has a Hamilton path from s' to t' } \}$ $\text{LONG-PATH} = \{(G,s,t,k) | \text{G has a simple path p from s to t, length(p) $\geq$ k} \}$ I'm trying ...
1
vote
1answer
217 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. ...