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\...
- 4,986
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 ...
- 35.6k
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]...
- 50.2k
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 ...
- 50.2k
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 ...
- 50.2k
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 ...
- 22.3k
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
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 ...
- 1,670
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 ...
- 35.6k
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 ...
- 20.5k
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,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 ...
- 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/...
- 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.
- 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 ...
- 3,094
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
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 ...
- 737
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,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 ...
- 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
(...
- 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 ...
- 50.2k
Only top scored, non community-wiki answers of a minimum length are eligible