7
$\begingroup$

I'm stuck on problem 9.4 from The Nature of Computation which reads:

Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this to a simple exponential, i.e., to solve TSP in $O(2^npoly(n))$ time. Can you do this without using an exponential amount of memory? Hint: work out Problems 3.31 and 3.32.

The first part is relatively straightforward. Given a graph, a set of previously visited vertices, a start vertex, and a target vertex, go through all neighbors of the start vertex that haven't been visited already and recursively solve the TSP starting from the neighbor. Then add the distance between start and neighbor to each and return the minimum. The base case, which returns $0$, occurs when $start = target$ and all vertices have been visited.
There are $2^n$ possible inputs for the set of previously visited vertices and $n^2$ possibilities for the start and target vertices. Since each call performs $O(n)$ work we get a dynamic programming algorithm with time complexity $O(2^n \cdot n^2 \cdot n) = O(2^npoly(n))$.

The tricky part is the exponential amount of memory, since the cache used by dynamic programming might grow exponentially large. What do the hints suggest? Problem 3.31 asked to solve Hamiltonian Path in $2^npoly(n)$ time, which could be done with the same idea I presented just now.
Problem 3.32 is more promising. It asked to show that the number of Hamiltonian paths from $s$ to $t$ can be computed in $2^npoly(n)$ time and $poly(n)$ space by evaluating the following expression:

$$\sum_{S\subseteq V}(-1)^{|S|}|q(S)|,$$

where $q(S)$ is the set of paths from $s$ to $t$ of length $n-1$ not visiting any vertex in $S$. ($|q(S)|$ can be computed relatively easily by iterating the adjacency matrix of $V\setminus S \quad n-1$ times.)
To prove this claim first observe that the number of Hamiltonian paths can be expressed like so:

$$|q(\emptyset)| - |\bigcup_{v_i}q(\{v_i\})|$$

which is the total number of paths minus the number of non-Hamiltonian paths, i.e. the paths not visiting some vertex $v_i$ (all of length $n-1$). Using the inclusion-exclusion-principle the second term can be rewritten as

$$|\bigcup_{v_i}q(\{v_i\})| = -\sum_{S\subseteq V\setminus \emptyset}(-1)^{|S|}|\bigcap_{v_i\in S}q(\{v_i\})|$$

Some further thought will then reveal the equivalence $q(A) \cap q(B) = q(A \cup B)$. (A path that avoids everything in $A$ and everything in $B$ also avoids everything in the union of $A$ and $B$. Similarly a path that avoids everything in $A$ or $B$ also avoids everything in $A$ and everything in $B$.)
With this our expression then becomes

$$|q(\emptyset)| + \sum_{S\subseteq V\setminus \emptyset}(-1)^{|S|}|q(S)| = \sum_{S\subseteq V}(-1)^{|S|}|q(S)|\qquad \Box$$

So how does this help finding the shortest traveling salesman tour? I see two options. Either use the algorithm laid out just now as a subroutine. Or reuse the ideas from the proof.
The first option seems pretty fruitless to me. Any instance of TSP that isn't defined on a fully connected graph can be converted to such an instance by adding in the missing edges with astronomically large weights. Counting the number of Hamiltonian paths on any subset $S$ of such a graph then becomes trivially easy. Every permutation of vertices is a Hamiltonian path so it's $|S|!$. Problem 3.32 seems of absolutely no help then.
The second approach breaks down because I can't find a way to fruitfully apply the inclusion-exclusion-principle. For that I'd need some sort of measure. But the one thing that suggests itself, the length of of the shortest traveling salesman tour on $S$, isn't one. $tsp(A \cup B) \neq tsp(A) + tsp(B)$ where $A \cap B = \emptyset$.

$\endgroup$
  • $\begingroup$ Is using convolution an option? $\endgroup$ – Pål GD Jul 14 '17 at 17:26
  • $\begingroup$ I've never seen the convolution being used in this context. How would you go about it? $\endgroup$ – Sebastian Oberhoff Jul 14 '17 at 17:28
  • $\begingroup$ I don't know from the top of my head, but I thought that the one of the first $O(2^n \text{poly}(n))$ algorithms for TSP in polynomial space was from Saving Space by Algebraization by Lokshtanov and Nederlof. I believe they use some convolution technique (over DFT or Möbius inversions), but I don't recall the technique. You can check out the paper. $\endgroup$ – Pål GD Jul 14 '17 at 17:35
  • $\begingroup$ Well that paper is rather dense. I'd probably need at least a week to get through that. And it's clearly not the solution the authors have in mind. $\endgroup$ – Sebastian Oberhoff Jul 14 '17 at 21:06
  • $\begingroup$ If you've got an end bit of path that is longer than the shortest full path, you can avoid taking it... Discarding that information could cut down on memory somewhat, but I don't see how that would make it less than exponential. $\endgroup$ – wizzwizz4 May 12 '18 at 14:26

Your Answer

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

Browse other questions tagged or ask your own question.