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,9052 gold badges22 silver badges34 bronze badges
20
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 ...
17
If we request that each $|V_i| \ge 3$, then this is the 2-factor problem,
see the book Combinatorial Optimization by Schrijver. If you allow $|V_i| = 2$,
then we can solve this by replacing each undirected edge by two directed ones and compute what is called a cycle-cover. This can be done in polynomial time by reduction to bipartite matching.
13
No. At least, no "nice" gadget for one crossover.
Let $(a, b)$ and $(x,y)$ be a cross we want to replace.
There are many cases for our graph, $G$, but we have to satisfy at least the following four. Case 1: there is at least one hamiltonian cycle, but none use either of the edges. Case 2: there is at least one cycle, and all cycles use exactly one of ...
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 ...
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.
8
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 ...
8
This is in PP.
Let $N$ be the size of the larger graph. We will define a predicate $f(P, b)$ where $P$ is a permutation of the numbers from 1 to $N$ and $b$ is a single bit.
First, define a predicate $H(G, P)$ where $G$ is a graph (with nodes labeled from 1 to $n \leq N$) and $P$ is a permutation of the numbers from 1 to $N$. Set $H$ to be true if and ...
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. ...
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 ...
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
Permutational Isomorphism of Permutation Groups, aka Permutation Group Conjugacy:
Input: Two lists of permutations in $S_n$, say $(\pi_1, \dotsc, \pi_k)$ and $(\rho_1, \dotsc, \rho_\ell)$
Output: A permutation $\pi \in S_n$ such that $\pi^{-1} \langle \pi_1, \dotsc, \pi_k \rangle \pi = \langle \rho_1, \dotsc, \rho_\ell \rangle$, or "NOT ISOMORPHIC"
(...
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
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 ...
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
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
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
(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 ...
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
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
13.9k4 gold badges51 silver badges133 bronze badges
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
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.
2
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
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 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 (...
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,...
1
If we didn't have the guarantee that there is at least one Hamiltonian path, the following would show NP-hardness.
Write $h(G)$ for the set of edges of the digraph $G$ that appear in every Hamiltonian path. The key fact is the following.
Lemma. For a digraph $G$, $h(G)=E(G)$ if, and only if, $G$ is a directed path or $G$ has no Hamiltonian ...
Only top voted, non community-wiki answers of a minimum length are eligible
