I read about local search / neighborhood search methods for the symmetric TSP and I'm not quite sure about a few things. The given example said:

Suppose we have an instance of the symmetric TSP with n nodes and the neighborhood $N^k$. Here $N^k$ is the $k$-change-neighborhood (delete $k$ edges and afterwards insert $k$ other edges).

We define $\gamma_{n, k}$ to be the number of possibilities to delete $k$ non-adjacent edges in a given tour.

If I understand this correctly, it should be as follows: $\gamma_{n, 0} = 1$, $\gamma_{n,1} = n$, $\gamma_{n, 2} = n(n - 3)$, and so on.

Is there a formula for $\gamma_{n,k}$?

  • $\begingroup$ So your question is: Given $n,k$, in how many ways can we select $k$ nonadjacent edges on a cycle of length $n$? $\endgroup$ – Yuval Filmus Nov 26 '17 at 15:41
  • $\begingroup$ yes, that's correct $\endgroup$ – balderdash Nov 26 '17 at 15:44
  • $\begingroup$ Sorry for the confusion, I should have thought a bit longer about how to formulate my actual question, thanks for clarification. $\endgroup$ – balderdash Nov 26 '17 at 15:46

Let $\delta_{n,k}$ be the number of ways to select $k$ nonadjacent edges on a path of length $n$. We can compute $\delta_{n,k}$ using a simple recurrence:

  • $\delta_{n,0} = 1$.
  • $\delta_{0,k} = 0$ for $k > 0$.
  • $\delta_{n,k} = \delta_{n-1,k} + \delta_{n-2,k-1}$, where the first term corresponds to the case in which the first edge is chosen, and the other to the case in which the first edge is not chosen.

We can solve this recurrence and obtain $\delta_{n,k} = \binom{n-k+1}{k}$. Indeed, this satisfies the two base cases, and the inductive case is just Pascal's identity $\binom{n-k+1}{k} = \binom{n-k}{k} + \binom{n-k}{k-1}$.

To compute $\gamma_{n,k}$, choose a first edge arbitrarily. If it is chosen, we are left with a choice of $k-1$ edges in a path of length $n-3$, and otherwise we are left with a choice of $k$ edges in a path of length $n-1$. In other words, $$ \gamma_{n,k} = \delta_{n-1,k} + \delta_{n-3,k-1} = \binom{n-k}{k} + \binom{n-k-1}{k-1}. $$ This gives $$ \begin{align*} \gamma_{n,0} &= 1, \\ \gamma_{n,1} &= \binom{n-1}{1} + \binom{n-2}{0} = (n-1) + 1 = n, \\ \gamma_{n,2} &= \binom{n-2}{2} + \binom{n-3}{1} = \frac{(n-2)(n-3)}{2} + (n-3) = \frac{n(n-3)}{2}, \end{align*} $$ and so on. Note that there is a difference in normalization: you count the edges with order, and I count them without order. This explains the factor of 2 in $\gamma_{n,2}$. In general, to take the order into account you need to multiply $\gamma_{n,k}$ by $k!$.

| cite | improve this answer | |

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.