Questions tagged [hamiltonian-path]
Questions on Hamiltonian paths, that is, paths that visit each vertex exactly once in a graph.
11
questions
3
votes
2
answers
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 ...
- 133
3
votes
2
answers
3k
views
CNF Generator for Factoring Problems
I've been reading these:
Fast Reduction from RSA to SAT
CNF Generator for Factoring Problems (Also have C code implementation)
I don't understand how the reduction from FACT to $3\text{-SAT}$ works. ...
- 899
6
votes
2
answers
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 ...
- 79
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 ...
- 283
5
votes
2
answers
9k
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 ...
5
votes
3
answers
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 ...
- 53
2
votes
1
answer
199
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' = (...
1
vote
1
answer
781
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 ...
- 345
0
votes
0
answers
135
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 ...
- 109
0
votes
0
answers
287
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, ...
- 659
0
votes
0
answers
74
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 - ...
- 421