13 votes

Problems with Unknown Single Exponential Time Agorithms

In the Graph Homomorphism problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\...
11 votes

Problems with Unknown Single Exponential Time Agorithms

Update 28 Sep 2020: This has been resolved by Wiebking in SODA '20, where he gave a $2^{O(n)}$-time algorithm, with no remaining dependence on $|G|$. (I'll leave up the rest of the answer for ...
10 votes

Problems with Unknown Single Exponential Time Agorithms

Computing the crossing number of a graph. Existing exact algorithms involve formulating it as an integer linear program with a number of variables cubic in the number of edges [Chimani et al, ESA 2008]...
8 votes
Accepted

A sufficient condition for non existance of hamiltonian cycle

Your question is kind of vague, and I don't know of a comprehensive listing of necessary conditions for Hamiltonicity (or equivalently sufficient conditions for non-Hamiltonicity). But for one such ...
8 votes

Applications of Hamiltonian Cycle Problem

One application involves stripification of triangle meshes in computer graphics — a Hamiltonian path through the dual graph of the mesh (a graph with a vertex per triangle and an edge when two ...
7 votes

Applications of Hamiltonian Cycle Problem

I think there are some applications in electronic circuit design/construction; for example Yi-Ming Wang, Shi-Hao Chen, Mango C. -T. Chao. An Efficient Hamiltonian-cycle power-switch routing for MTCMOS ...
6 votes

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

The probability that a random graph with $n$ nodes and $cn\log n$ edges contains a Hamiltonian circuit tends to $1$ as $n\rightarrow\infty$ (and for sufficiently large $c$) (Pósa 1976). Since an ER ...
  • 1,448
5 votes

Applications of Hamiltonian Cycle Problem

(Variants of the) TSP show(s) up routinely in several routing and scheduling problems (think of the route planned for a UPS truck out of delivering packages, for instance). But a great place to learn ...
  • 316
4 votes
Accepted

On the paper "Quantum Computing Hamiltonian cycles"

I emailed the author. He replied "yes that paper is wrong!". He has lost the passwords to remove it from the web.
  • 1,955
4 votes

Problems with Unknown Single Exponential Time Agorithms

The problem of testing whether a given integer linear program $L$ with $n$ variables has a feasible solution can be solved using $n^{2.5n+o(n)}\cdot |L|$ arithmetic operations. It is a major open ...
4 votes

Problems with Unknown Single Exponential Time Agorithms

Tensor Isomorphism. The best-known algorithm for 3-Tensor Isomorphism over $\mathbb{F}_q$ takes time $q^{\Theta(n^2)}$, and over $\mathbb{R}$ or $\mathbb{C}$ takes times $2^{\Theta(n^2)}$. (The same ...
4 votes

List of strongly NP-hard problems with numerical data

Here is a strongly $NP$-complete problem (with numerical data as you requested): Schur Triples problem: Input: list of 3N distinct positive integers Question: Is there a partition of the list into ...
3 votes
Accepted

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

Yes, it is still $NP$ complete. This is because of: Claim: All Hamiltonian cycles on maximal planar graphs are balanced. Proof: This is a special case of Grinberg's theorem: https://en.wikipedia.org/...
  • 1,439
3 votes

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

As RB mentioned, this is the Orienteering problem. For points on a plane, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.5979 gives a PTAS.
  • 31
3 votes

What are the known classes of undirected graphs such that every graph belonging to that class is guaranteed to have a Hamiltonian Path?

A good resource to answer questions like this is graphclasses.org. You find the graph class you care about -- in this case, Hamiltonian graphs. Then check the maximal subclasses section, and ...
  • 2,313
2 votes
Accepted

Finding a Hamiltonian cycle from perfect matching of a bipartite graph

If $G$ has a disjoint vertex cycle cover then I agree that $H$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $H$ exactly). I think the ...
  • 1,207
2 votes
Accepted

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

This problem is known as the (Undirected) Orienteering problem (I'm unaware of any work that examined distances that come from 2D Euclidean embedding). It is NP-hard (and moreover, $APX$-hard) and ...
  • 9,378
2 votes

Hamiltonian Cycle as an integer linear programming problem

I know this is old, but-- First, make this a 'directed' cycle: only one $e_{ij}$ is true on each vertex, so that $v_i = 1$. This will enable a sort of useful indexing on the cycle. Next, create ...
2 votes

Best Hamiltonian Cycle Problem solver

I found myself having to find a Hamilton path in a graph of 200 vertices (what you called "nodes"). My first idea was to use the Hamilton path solver in Maxima ( http://maxima.sourceforge.net/docs/...
2 votes

Problems with Unknown Single Exponential Time Agorithms

In a recent paper by Fomin et al. (Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds) it is shown that computing the Hadwiger number of a graph has the complexity ...
1 vote

K-fold Traveling salesman problem - A variant of TSP

There was a paper on the arxive last month, dealing with this generalization of the TSP: The multi-stripe travelling salesman problem Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger (...
  • 5,742

Only top scored, non community-wiki answers of a minimum length are eligible