際際滷

際際滷Share a Scribd company logo

Tsp is NP-Complete

Download as PPTX, PDF
Emre Can Kucukoglu
Emre Can Kucukoglu

This document discusses how the Traveling Salesman Problem (TSP) is NP-Complete. It first shows that TSP is in NP by describing a nondeterministic polynomial time algorithm to solve it. It then reduces the known NP-Complete Hamiltonian Cycle problem to TSP by constructing an equivalent instance of TSP from any Hamiltonian Cycle problem instance in polynomial time, showing that Hamiltonian Cycle is polynomial time reducible to TSP. Therefore, since any problem in NP can be reduced to Hamiltonian Cycle and Hamiltonian Cycle can be reduced to TSP, any problem in NP can be reduced to TSP, proving that TSP is NP-Complete.

1 of 11
Downloaded 199 times
TSP NP-Complete Emre Can Kucukoglu eckucukoglu@gmail.com 16.01.2016
Traveling Salesman Problem Given n cities 1, 2, 3, , and integer distances , between any two cities . TSP asks for the total distance of the shortest tour of the cities. Decision version of TSP asks if there is a tour with a total distance at most B, where B is an input.
TSP: formal description TSP = { <G, d, B> : G=(V, E) is a complete undirected graph, d is an edge cost function from VxVZ+ {0}, B Z, G has a Hamiltonian cycle with cost B }
TSP NP-Complete ? To prove that TSP NP-Complete, First, we must show that there exists a nondeterministic algorithm in polynomial time that solves TSP. TSP NP Then, we will reduce the undirected Hamiltonian cycle, which is a known NP-complete problem, to TSP: HAM-CYCLE TSP
Nondeterministic algorithm for TSP The following procedure is a polynomial time non-deterministic algorithm that terminates successfully iff an ordering of n- cities are distinct and sum of distances between pairs are less than or equal to B. The complexity of this non- deterministic algorithm is O(n). So that; TSP NP
Hamiltonian Circuit Problem Find a tour of a given unweighted graph that simply starts at one vertex and goes through all the other vertices and ends at the starting vertex. Note that the input graph G to a Hamiltonian Cycle problem need not be a complete graph connecting all vertices. Hamiltonian circuit is a known NP-Complete problem.
To transform Hamiltonian circuit/cycle problem to TSP, Create a graph G = (V, E) from Hamiltonian cycle instance G = (V, E), G is a complete graph, Edges in E also in E have an edge cost 0, All other edges in E have an edge cost 1. HAM-CYCLE TSP
Take any instance G = (V, E) for the Hamiltonian cycle problem, Convert it into an instance G=(V, E = VV, d), B = 0 of TSP, , = { 0 if edge (, ) E, 1 otherwise } Time complexity of reduction is O(2) as there n(n-1)/2 edges on a complete graph. HAM-CYCLE TSP
Problem: Is there a TSP on G with total edge cost = 0 ? If G has a Hamiltonian circuit, algorithm will return "yes" on input (G, C), If there is no Hamiltonian circuit in G, algorithm will return "no" on input (G, C). If G has a cycle with cost = 0, every edge of that cycle has a cost = 0, thus G has a Hamiltonian cycle. If Hamiltonian cycle does not exist, then there is no simple cycle in G, that visits every vertex exactly once. Suppose that TSP has a yes answer. Then, there is a cycle that visits every vertex once with total cost = 0. Since negative distance cost is not possible, every edges have cost = 0, which implies that these edges are in the Hamiltonian Circuit graph. It is a contradiction. HAM-CYCLE TSP
TSP NP-Complete It is well known that Hamiltonian Circuit is NP-Complete, every problem in NP reduces to Hamiltonian Circuit in polynomial time. We have reduced Hamiltonian Circuit to TSP in polynomial time, it indicates that every problem in NP reduces to TSP is polynomial time, since the sum of two polynomials is also a polynomial.
References http://www.csie.ntu.edu.tw/~lyuu/complexity/2004/c_20040929.pdf http://web.calstatela.edu/faculty/jmiller6/2014spring- cs312/lectures/Lecture10.pdf https://www.quora.com/Why-is-the-traveling-salesman-problem-NP- complete/answer/Luke-Benning

More Related Content

Tsp is NP-Complete

  • 1. TSP NP-Complete Emre Can Kucukoglu eckucukoglu@gmail.com 16.01.2016
  • 2. Traveling Salesman Problem Given n cities 1, 2, 3, , and integer distances , between any two cities . TSP asks for the total distance of the shortest tour of the cities. Decision version of TSP asks if there is a tour with a total distance at most B, where B is an input.
  • 3. TSP: formal description TSP = { <G, d, B> : G=(V, E) is a complete undirected graph, d is an edge cost function from VxVZ+ {0}, B Z, G has a Hamiltonian cycle with cost B }
  • 4. TSP NP-Complete ? To prove that TSP NP-Complete, First, we must show that there exists a nondeterministic algorithm in polynomial time that solves TSP. TSP NP Then, we will reduce the undirected Hamiltonian cycle, which is a known NP-complete problem, to TSP: HAM-CYCLE TSP
  • 5. Nondeterministic algorithm for TSP The following procedure is a polynomial time non-deterministic algorithm that terminates successfully iff an ordering of n- cities are distinct and sum of distances between pairs are less than or equal to B. The complexity of this non- deterministic algorithm is O(n). So that; TSP NP
  • 6. Hamiltonian Circuit Problem Find a tour of a given unweighted graph that simply starts at one vertex and goes through all the other vertices and ends at the starting vertex. Note that the input graph G to a Hamiltonian Cycle problem need not be a complete graph connecting all vertices. Hamiltonian circuit is a known NP-Complete problem.
  • 7. To transform Hamiltonian circuit/cycle problem to TSP, Create a graph G = (V, E) from Hamiltonian cycle instance G = (V, E), G is a complete graph, Edges in E also in E have an edge cost 0, All other edges in E have an edge cost 1. HAM-CYCLE TSP
  • 8. Take any instance G = (V, E) for the Hamiltonian cycle problem, Convert it into an instance G=(V, E = VV, d), B = 0 of TSP, , = { 0 if edge (, ) E, 1 otherwise } Time complexity of reduction is O(2) as there n(n-1)/2 edges on a complete graph. HAM-CYCLE TSP
  • 9. Problem: Is there a TSP on G with total edge cost = 0 ? If G has a Hamiltonian circuit, algorithm will return "yes" on input (G, C), If there is no Hamiltonian circuit in G, algorithm will return "no" on input (G, C). If G has a cycle with cost = 0, every edge of that cycle has a cost = 0, thus G has a Hamiltonian cycle. If Hamiltonian cycle does not exist, then there is no simple cycle in G, that visits every vertex exactly once. Suppose that TSP has a yes answer. Then, there is a cycle that visits every vertex once with total cost = 0. Since negative distance cost is not possible, every edges have cost = 0, which implies that these edges are in the Hamiltonian Circuit graph. It is a contradiction. HAM-CYCLE TSP
  • 10. TSP NP-Complete It is well known that Hamiltonian Circuit is NP-Complete, every problem in NP reduces to Hamiltonian Circuit in polynomial time. We have reduced Hamiltonian Circuit to TSP in polynomial time, it indicates that every problem in NP reduces to TSP is polynomial time, since the sum of two polynomials is also a polynomial.