1
$\begingroup$

Recursive definition for travelling salesman problem can be written like this :-

T(i,S)=min((i,j)+T(j,S-{j})) for all j belonging to S, when S is not equal to NULL

T(i,S)=(i,S) when S is equal to NULL

Here, T(i,S) denotes the tour starting from i covering all vertices in Subset S and then travel back to i.

I built the recursive tree and calculated the subproblems at each level. For k elements, number of subproblems comes out to be :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+(n-1)(n-2)(n-3)......(n-k).

For k=4, number of subproblems at level 1=3,level 2=6,level 3=6 For k=4, number of subproblems at level 1,2 and 3 are 3,6 and 6 respectively.

I tried to solve it but couldn't find the actual solution but it can be seen clearly that the time complexity is factorial. Now, in the recursion tree there are repeated function calls at the last level which we use to improve our time complexity using dynamic programming. Now, half of the function calls at last level are repeated that would reduce the number of subproblems to :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+((n-1)(n-2)(n-3)......(n-k))/2.

But, I think the time complexity is still factorial. I read on various resources that time complexity of travelling salesman problem using dynamic programming is $O(n^2*2^n)$ which is exponential.

Is there something wrong in my analysis? Can anyone prove how the time complexity comes out to be $O(n^2*2^n)$ ?

$\endgroup$
1
$\begingroup$

When solving TSP using dynamic programming you get something akin to the following:

TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}

(neighbors only returns target as a viable neighbor if no other choice is available)

This algorithm recursively finds the shortest tour starting from each neighbor and returns the minimum of those. If you do all this with dynamic programming you can calculate the amount of work you're doing like so:
There are $n$ possible start vertices and $2^n$ possible subgraphs. So this function will be called on at most $n\cdot2^n$ distinct arguments (the target never changes). Each call performs at most $O(n)$ work (there are at most $n$ neighbors). Hence the total work you're doing is $O(n^2\,2^n)$.

$\endgroup$
  • $\begingroup$ What would be the time complexity if I am using adjacency list representation and $E=O(V)$ $\endgroup$ – shiwang Jun 17 '18 at 13:32
  • $\begingroup$ That doesn't make a difference. Either way, you're iterating through $O(n)$ neighbors on each call to TSP. This should take $O(n)$ time in any reasonable data structure. $\endgroup$ – Sebastian Oberhoff Jun 17 '18 at 16:45
  • $\begingroup$ And one more thing, if the time complexity using dp is $O(n^2*2^n)$., we are getting the same time complexity using only recursive approach. Then, why are we using dynamic programming here. It takes up alot of space. Although, it reduces the number of problems we have to solve but it doesn't help to reduce the time complexity. $\endgroup$ – shiwang Jun 17 '18 at 18:01
  • $\begingroup$ $O(n^2 2^n)$ is better than $O(n!)$. Sure, you're not getting something subexponential. But TSP is NP-hard. So that's hardly a surprise. $\endgroup$ – Sebastian Oberhoff Jun 18 '18 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.