Nearest Neighbor Traveling Salesman Heuristic (NNTSH)

Input

A finite set $C = \{C_1, \ldots, C_n\}$ of cities, and a distance matrix $D$ with entries $(d_{ij})$ that are positive integers ($1 \leq i, j \leq n$), and two distinguished vertices $s$ and $l$.

Problem

Does the nearest neighbor tour starting at s visit l as the last vertex before completing the tour at s?

Definitions

The nearest neighbor tour is a greedy heuristic that always chooses the nearest unvisited vertex as the next vertex on the tour.

Status

$\P$-complete (Kindervater, Lenstra, and Shmoys [1]).

Remarks

The reduction to show hardness is from NANDCVP.

The nearest merger, nearest insertion, cheapest insertion, and farthest insertion heuristics are all $\P$-complete [1]. The double minimum spanning tree and nearest addition heuristics are in $\NC$ [1]. See TS2Opt.