Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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\...
Serge Gaspers's 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 ...
Joshua Grochow's 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]...
David Eppstein's 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 ...
David Eppstein's 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 ...
Marzio De Biasi's user avatar
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 ...
kbala's user avatar
  • 326
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 ...
Christian Komusiewicz's 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 ...
Joshua Grochow's 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.
joro's user avatar
  • 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/...
Elle Najt's user avatar
  • 1,469
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 ...
GMB's user avatar
  • 2,403
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(...
JimN's user avatar
  • 1,318
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/...
Chris Tennant's user avatar
2 votes

Hamiltonian Cycle as an integer linear programming problem

Here's a simple ILP that nobody has mentioned yet. Given the undirected graph $G=(V, E)$, use binary variables $\pi_{iv}$ for $(i, v)\in [n]\times V$, where $n=|V|$. Variable $\pi_{iv}$ indicates ...
Neal Young's user avatar
  • 10.8k
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 ...
Alex Meiburg's user avatar
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 ...
Michael Lampis's user avatar
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 ...
M.Monet's user avatar
  • 1,429
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 (...
Gamow's user avatar
  • 5,772

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