21
Here is a simple reduction for the TSP problem to the metric TSP problem:
For the given TSP instance with $n$ cities, let $D(i,j) \geq 0$ denote the distance between $i$ and $j$. Now let $M = \max_{i,j} D(i,j)$. Define the metric TSP instance by the distances $D'(i,j) := D(i,j)+M$. To see that this gives a metric TSP instance, let $i,j,k$ be arbitrary. Then ...
answered Oct 22 '12 at 15:02
Kristoffer Arnsfelt Hansen
3,9152 gold badges23 silver badges34 bronze badges
21
From the comments above: the Hamiltonian cycle problem remains NP-complete even in grid graphs with max degree 3 [1], but in these graphs every traversal of a node requires two edges and at most one edge remains unused, so a node cannot be traversed twice by an Eulerian path.
So apparently there is an immediate reduction from the Hamiltonian cycle problem ...
13
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\in E(G)$ we have that $h(u) h(v)\in E(H)$.
The problem can be solved in time $O^*(|V(H)|^{|V(G)})$ by a brute-force algorithm (the $O^*$-notation hides factors ...
11
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 historical purposes.)
Permutational Isomorphism of Permutation Groups, aka Permutation Group Conjugacy:
Input: Two lists of permutations in $S_n$, say $(\pi_1, \dotsc, ...
11
For undirected graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that
$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N-N^c$.
Karger Motwani Ramkumar 1997
For directed graphs, you ...
10
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]. Even for the restricted one-page crossing number, in which the vertices are placed on the boundary of a disk and the edges interior to the disk, known ...
8
It is an open problem to lower bound the difference between two distinct Euclidean TSP tours by an inverse polynomial in the input size. Such a lower bound would show that Euclidean TSP is an NP optimizaition problem, which is not known.
Let us assume that a Euclidean TSP instance is given by a collection of points in $(\mathbb{Z} \cap [-N, N])^2$ (i.e. ...
8
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 condition, commonly used to prove non-Hamiltonicity of certain planar graphs, see Grinberg's theorem.
Another necessary condition, valid for all graphs (not just ...
8
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 triangles share an edge) can be a helpful way to organize data and reduce communication costs.
7
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 designs. 2012
Abstract: Multi-threshold CMOS (MTCMOS) is currently the most popular methodology in industry for implementing a power gating design, which can ...
7
A polytime algorithm that can find such a collection of edges even in the promise version of this problem can be used as a blackbox to solve the Hamiltonian Path problem in polynomial time, and thus this promise problem is NP-Hard under Cook reductions. The idea here is to use the algorithm for solving the promise problem on a sequence of graphs, many (but ...
6
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 random graph has $\Omega(n^2)$ edges, it is almost certainly Hamiltonian as $n\rightarrow \infty$, even without the constraint on the minimal degree.
6
Assuming that $p$ and $q$ are fairly large, one would expect that the expected length would mainly depend on the density, with some correction term depending on the perimeter. So it would, to first order, be a function of the following form.
$$ L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$$
Now, you could use experiments on smaller-size problems to ...
5
(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 about several applications of the TSP is Chapter 3 of the book In Pursuit of the Traveling Salesman:
Mathematics at the Limits of Computation by Bill Cook. In ...
5
Describing connectivity in integer programming is not as straightforward as the rest of the reduction, I think.
However, it is quite clean to reduce HAMCYCLE to SAT (e.g. here), and it is very clean to reduce SAT to integer programming. I think you will end up with a system that is not all that complicated. Perhaps it is worth doing so than busting your ...
4
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 N triples $(a_i, b_i, c_i)$ such that $a_i + b_i= c_i$ for each triple $i$?
The condition that all numbers must be distinct makes the problem very interesting ...
answered Jan 21 '15 at 17:29
Mohammad Al-Turkistany
20k4 gold badges54 silver badges136 bronze badges
4
I tried to write a formal proof of the NP-completeness of Problem 1 (Crazy Frog Problem, CFP).
It remains NP-complete even if restricetd to a one dimensional board (1-D Crazy Frog Problem, 1-D CFP) or to a one dimensional board without blocked cells, and there is an immediate reduction from the 1-D CFP without blocked cells to the Permutation Reconstruction ...
4
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 problem in combinatorial optimization and parameterized algorithms whether this can be improved to a running time of $2^{O(n)}\cdot |L|^{O(1)}$.
It can be easily ...
4
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 is true for $d$-Tensor Isomorphism for $d \geq 3$, where a factor of $d-2$ is hidden in the $\Theta(\cdot)$ in the exponent. But the $d=3$ case is already TI-...
4
I emailed the author.
He replied "yes that paper is wrong!".
He has lost the passwords to remove it from the web.
3
Something has gone wrong, here. Let us start with the basic definitions.
A Hamiltonian cycle is a cycle is an enumeration $v_1, \dots, v_n$ of the vertices of a graph such that there is an edge from $v_i$ to $v_{i+1}$ for $1\leq i<n$ and an edge from $v_n$ to $v_1$.
In the Traveling Salesman Problem (TSP), we are given $n$ cities and, for every pair of ...
3
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/wiki/Grinberg%27s_theorem
3
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.
2
I believe the answer is no and here is why.
Assume that I can efficiently find a hamiltonian cycle of minimum weight in $G'$ given a hamiltonian cycle of minimum weight in $G$. I can use this procedure to find a hamiltonian cycle in any graph, say $A$.
The procedure would work like this. Take $A$ and add vertices and edges (with weight $0$) such that a ...
2
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/manual/de/maxima_50.html#IDX2257 ), but it wasn't able to solve it. Luckily, a few years ago, I used to use SAT solvers to solve difficult logic grid puzzles (...
2
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 profile this question is looking for. Namely, the problem can be solved in $n^{O(n)}$ fairly easily, but cannot be solved in $n^{o(n)}$ unless the ETH is false. ...
2
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 there exists a $2+\epsilon$ approximation for it.
1
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
(Submitted on 20 Sep 2016)
https://arxiv.org/abs/1609.09796
The problem does not seem to have a particular name in the literature.
1
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 path of $k$ nodes starting at any node. The example of $K_{k-1}$, which has no $k$-path and has minimum degree $k-2$, shows that this is tight.
1
A partial answer to the easier of my two questions:
If an edge $x\rightarrow y$ is 'obviously' part of all Hamiltonian paths because it is the only edge into vertex $y$, then all other edges from $x$ cannot be in any Hamiltonian cycle, because this would imply the path visits $x$ more than once. Thus, these other edges from $x$ can be removed from the graph,...
Only top voted, non community-wiki answers of a minimum length are eligible
