A path in a graph is said to be Hamiltonian if it visits each vertex exactly once.

learn more… | top users | synonyms

9
votes
1answer
314 views

Is the longest trail problem easier than the longest path problem?

The longest path problem is NP-hard. The (typical?) proof relies on a reduction of the Hamiltonian path problem (which is NP-complete). Note that here the path is taken to be (node-)simple. That is, ...
5
votes
3answers
417 views

Is there an efficient algorithm for finding edges that are part of all hamiltonian paths?

I'm wondering if there is any algorithm known for finding edges in a graph that are part of all hamiltonian paths (operating under the assumption that the graph has at least one such path). Failing ...
-5
votes
1answer
299 views

Self-avoiding walk in Graph [closed]

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...
3
votes
1answer
179 views

Minimum offset while measuring TSP paths

I have Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I am trying to solve TSP with brute algorithm, and I want to ...
0
votes
0answers
237 views

Formulation of the k-TSP as an integer programming problem?

Specifically, in a complete graph, I'm trying to find the simple path with $k$ nodes that minimizes the sums of their vector edge weights. Additionally, the solution should be Pareto efficient ...
6
votes
1answer
336 views

Two Hamiltonian path problem variants

While formalizing the gadgets for the proposed reduction of the question Efficient algorithm for existence of permutation with differences sequence? the following problems came to my mind: Problem 1 ...
3
votes
1answer
138 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')$ ...
4
votes
1answer
171 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 ...
4
votes
2answers
764 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 ...
4
votes
0answers
205 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 ...
5
votes
1answer
660 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
496 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 ...
9
votes
1answer
223 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
202 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 ...
2
votes
1answer
217 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 ...
6
votes
3answers
1k 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
13
votes
3answers
673 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 ...
20
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
256 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
311 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
353 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
632 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
410 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, ...