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\...
user avatar
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 ...
user avatar
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]...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 316
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 1,945
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 ...
user avatar
  • 2,183
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/...
user avatar
  • 1,429
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.
user avatar
  • 31
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 ...
user avatar
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/...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 9,348
1 vote
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 ...
user avatar
  • 1,095
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 (...
user avatar
  • 5,712
1 vote

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

I don't know about the weakest possible conditions, but if a graph has a subgraph with minimum degree $k-1$ (that is, if its degeneracy is at least $k-1$) then a greedy algorithm can easily find a ...
user avatar

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