# Tagged Questions

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

447 views

### Applications of Hamiltonian Cycle Problem

The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively. I am looking for applications of the HamCycle and TSP. What are ...
205 views

### Problems with Unknown Single Exponential Time Agorithms

I'm looking for examples of problems for which it is easy to get algorithms running in time $2^{O(n\log n)}$, or $2^{O(n^c)}$ for some $c>1$ but for which it is not known whether there is an ...
164 views

### A sufficient condition for non existance of hamiltonian cycle

I think i have a sufficient condition for non existance of hamiltonian cycle in a graph, I want to check if it has already been found, I tried googling for it and didnt find anything so far, how can i ...
102 views

### What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

Given a random graph by the Erdős–Rényi model, if the minimal node degree is greater than 1 (or $\geq 2$), or randomly select a graph from the graphs with node degrees greater than 1 ($\geq 2$), what'...
129 views

### Connecting partial paths to form a hamiltonian cycle [closed]

For an undirected graph that consists of partial paths such that each vertex is a part of one of those paths and that there are edges between all the paths, is there an efficient algorithm to connect ...
360 views

### Best Hamiltonian Cycle Problem solver

What is the best Hamiltonian Cycle Problem (HCP) solvers available in the market? Googling so far shows that there is one created by Flinders University that can solve at most 5000 node instances. I ...
179 views

### Hamiltonian cycle on a subset of 2D points, constrained by maximum total length

We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a ...
186 views

### Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence?

In the well studied problem of Hamiltonicity, several papers/theorems gave sufficient "degree conditions" for the existence of Hamiltonian path in a graph. These include: Dirac's theorem , 1952, ...
1k 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, ...
614 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 ...
498 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 ...
194 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 ...
422 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 ...
161 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')$ ...
212 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 ...
2k 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 ...
949 views

### List of strongly NP-hard problems with numerical data

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 ...
2k views

353 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 ...
425 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 ...