This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...

The question concerns the TSP problem (with fixed start- and end-vertex). The graph is the graph induced on the ball in an infinite grid. More precisely, the vertices are $B_n = \lbrace (x,y) \in \mathbb{Z}^2 \mid |x|+|y| \leq n \rbrace$ and two vertices $v'=(x',y')$ and $v=(x,y)$ are neighbours if $|x-x'| +|y-y'|=1$.

$\textbf{Questions:}$ For two distinct vertices $v$ and $v'$ in $B_n$ (say $n>2$) let $p_{v,v'}$ be the shortest path between these vertices which goes at least once through any vertex. Let $|p|$ be the length of a path $p$.

  • $\textbf{(1)}$ What is the smallest $k$ (possibly depending on $n$ but independent of $v$ and $v'$) such that $|p_{v,v'}| \leq |B_n| + k$? Can $k$ be chosen independently of $n$?

  • $\textbf{(2)}$ What is the smallest $\ell$ (possibly depending on $n$) such that $\max_{v,v'} |p_{v,v'}| \leq \min_{v,v'} |p_{v,v'}|+\ell$? Can $\ell$ be chosen independently of $n$?

For rectangles (of sides $m \times n$) instead of balls, it is known that $k$ and $\ell$ can be chosen to be (respectively) $1$ and $2$ as soon as $m,n \geq 3$. I have the impression that this is sharp contrast to the case of a ball ($\ell$ might still be uniformly bounded but $k$ is probably $\simeq An+B$)

  • $\begingroup$ So, by "ball", you mean the ball in the $\ell_1$-norm, that is, a square with sides of angles $\pi/4$ with respect to the axes? $\endgroup$ – Jan Kyncl Jun 20 '14 at 7:23
  • $\begingroup$ Regarding question 2), which paths do you consider? What is a "path", actually, by your definition? $\endgroup$ – Jan Kyncl Jun 20 '14 at 7:30
  • 1
    $\begingroup$ Sorry fot the delay: 1- yes, the ball is the one from the graph (or $\ell^1$) metric. 2- Here by path between $v$ and $v'$ I mean a "walk" i.e. a sequence of vertices $\lbrace v_i \rbrace_{i=0}^\ell$ with $v_0 = v$ and $v_\ell = v'$ and, for any $1 \leq j \leq \ell$ one has that $v_j$ is a neighbour of $v_{j-1}$. The length of this path is $\ell$. $\endgroup$ – ARG Jun 22 '14 at 12:32
  • $\begingroup$ Actually, if one uses the definition of "path" as «a subgraph isomorphic to a "segment" graph», then there are lots of cases where the vertices may not all covered. The difference between rectangle and ball is still striking there. In this definition of path, a rectangle has a path which misses at most two vertices (independently of start and end vertex) whereas, in a ball, lots of points are missed by this kind of path. $\endgroup$ – ARG Jun 22 '14 at 12:38
  • $\begingroup$ I see... so then it might be a good idea to edit the question and replace "path" by "walk", as a "path" in a graph usually means that it visits no vertex more than once. $\endgroup$ – Jan Kyncl Jun 23 '14 at 7:15

For question (1), $k$ grows linearly with $n$, so it cannot be chosen independently.

Color the vertices of the grid black and white, so that the vertices $(x,y)$ with $x+y$ even are black and the remaining vertices are white. Clearly, every edge of the graph has one end black and the other end white. Therefore, on every walk, the number of black and white vertices differs by at most one.

Now it is easy to see that $B_n$ has $n^2$ vertices of one color and $(n+1)^2$ vertices of the other color. So every walk visiting all vertices of $B_n$ has at least $|B_n|+2n$ vertices, that is, at least $|B_n|+2n-1$ edges. Now, if the two vertices $v$ and $v'$ belong to the minor color, then the length of the walk from $v$ to $v'$ must be at least $|B_n|+2n+1$.

The lower bound $|B_n|+2n-1$ is achieved by a spiral-like walk that starts at $(0,n)$ and ends at $(0,0)$ for $n$ even, or $(1,0)$ for $n$ odd.

The case of arbitrary pair of endpoints remains to be solved. But clearly, $l$ is not larger than $2n+1$ (one can start with the spiral-like walk, perhaps rotated or reflected, and extend it to the required endpoints).

The existence of the spiral walk matching the necessary lower bound also implies that $k=l+2n-1$.


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.