A path in a graph is said to be Hamiltonian if it visits each vertex exactly once.
3
votes
1answer
101 views
Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$
Say I have an undirected, weighted graph $G=(V,E)$ and I know a hamiltonian cycle of minimum weight in that graph. Can I use that information to efficiently find a hamiltonian cycle in $G'=(V',E')$ ...
2
votes
1answer
133 views
Complexity reductions to Hamiltonian Path?
I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path.
Do ...
3
votes
2answers
283 views
Hamiltonian Cycle as an integer linear programming problem
I'm trying to do reduce Hamiltonian Cycle to integer linear programming. Here's my idea:
Create variables $e_{ij}$ for every edge $(i,j)$ in the graph. Require each $$e_{ij}\in \{0,1\}$$. Create ...
2
votes
0answers
135 views
listing of strongly NP problems
I am looking for strongly NP hard problems for a reduction.
So far I have found the following problems:
3-partition problem
bin-packing problem
Numerical 3-dimensional matching
TSP
Any NP-complete ...
1
vote
1answer
267 views
Guidelines to reduce general TSP to Triangle TSP
I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie:
$D(a, b) \leq ...
9
votes
1answer
320 views
What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?
$k$ distinct points are selected randomly from a $p\times q$ grid. (Obviously $k\leq p\times q$ and is a given constant number.) A complete weighted graph is built from these $k$ points such that ...
8
votes
1answer
187 views
Hamilton Decomposition Decision Problem
Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph ...
20
votes
1answer
1k views
I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)
It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle.
Is there a nice gadget that will, ...
3
votes
1answer
165 views
A decision problem related to the problem of counting Hamiltonian cycles
Define a decision problem H as follows. The input of H is a pair (G1,G2) of graphs, and the problem is to verify whether the number of Hamiltonian cycles in G1 is greater than the number of ...
1
vote
1answer
200 views
Searching for name of equivalence property in hamiltonian paths
This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up.
Given a hamiltonian path, any subpath ...
4
votes
3answers
845 views
Cubic graphs and hamiltonian paths
I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you
11
votes
3answers
560 views
Classes of graphs with easy Hamiltonian cycle but NP-hard TSP
The Hamiltonian Cycle Problem (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The Travelling Salesman Problem (TSP) consists in finding a cycle that goes ...
19
votes
2answers
1k views
Hamiltonicity of k-regular graphs
It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, ...
3
votes
2answers
231 views
Complexity of the Hamiltonian Subcycle problem
The problem is as follows:
Given a graph $G$, find a (vertex)
disjoint set of cycles $C$ on $G$ such
that every vertex is visited by a
cycle exactly once.
My question is then: what is the ...
6
votes
2answers
271 views
On the class of the FNP version of the Hamiltonian Cycle problem
This post is linked to: http://cstheory.stackexchange.com/questions/1088/fnp-complexity-class
Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems ...
3
votes
3answers
315 views
FNP complexity class
Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity)
However, that isn't sufficient for me to ...
2
votes
3answers
563 views
Best bounds for the longest path optimization problem in cubic Hamiltonian graph?
optimization problem
Input: cubic Hamiltonian graph
feasible solution: A simple path
measure to optimize: length of the simple path
Design a polynomial-time algorithm that outputs the longest path ...
5
votes
1answer
288 views
What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?
A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,
...
