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\...
- 5,066
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 ...
- 36.9k
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.9k
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.9k
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.6k
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,700
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 ...
- 36.9k
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
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
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,393
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,416
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 ...
- 807
2
votes
Accepted
Complexity of finding a path visiting all leaves on a tree while respecting a distance bound
As the comments have suggested, you are looking for a Ham Path through a set nodes in the $k$-leaf power graph of this tree. That is, given your tree $T$ and a distance $k$, form a graph $G$ where $V(...
- 1,276
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,227
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,772
Only top scored, non community-wiki answers of a minimum length are eligible