# Converting MST to TSP Path by Branch Elimination
## 1 Introduction  
The classical _closed loop_ variant of _travelling salesman problem_ (TSP) visits all the nodes and then returns to the start node by minimizing the length of the tour. _Open loop TSP_ is slightly different variant, which skips the return to the start node. They are both NP-hard problems [1], which means that finding optimal solution fast can be done only for very small size inputs. The open loop variant appears in mobile-based orienteering game called _O-Mopsi_ ([[http://cs.uef.fi/o-mopsi/](http://cs.uef.fi/o-mopsi/)]([http://cs.uef.fi/o-mopsi/](http://cs.uef.fi/o-mopsi/))) where the goal is to find a set of real-world _targets_ with the help of smartphone navigation [2]. This includes three challenges: (1) Deciding the order of visiting the targets, (2) navigating to the next target, and (3) physical movement. Unlike in classical orienteering where the order of visiting the targets is fixed, O-Mopsi players optimize the order while playing. Finding the optimal order is not necessary but desirable if one wants to minimize the tour length. However, the task is quite challenging for humans even for short problem instances. In [2], only 14% of the players managed to solve the best order among those who completed the tour. Most players did not even realize they were dealing with TSP problem. _Minimum spanning tree_ (MST) and TSP are closely related algorithmic problems. In specific, open loop TSP solution is also a spanning tree but not necessarily the minimum spanning tree; see Figure 1. The solutions have the same number of links (\(n-1\)) and they both minimize the total weight of the selected links. The difference is that TSP does not have any branches. This connection is interesting for two reasons. First, finding optimal solution for TSP requires exponential time while optimal solution for MST can be found in polynomial time using greedy algorithms like _Prim_ and _Kruskal_, with time complexity very close to O(\(n^{2}\)) with appropriate data structure. The connection between the two problems have inspired researchers to develop heuristic algorithms for the TSP by utilizing the minimum spanning tree. Classical schoolbook algorithm is _Christofides_[3, 4], which first creates an MST. More links are then added sothat the Euler tour can be constructed. Travelling salesman tour is obtained from the Euler tour by removing nodes that are visited repeatedly. This algorithm is often used as classroom example because it provides upper limit how far the solution can be from the optimal solution in the worst case. Even if the upper limit, 50%, is rather high for real life applications, it serves as an example of the principle of _approximation algorithms_. MST has also been used to estimate lower limit for the optimal TSP solution in [5], and to estimate the difficulty of a TSP instance by counting the number of branches [6]. [PERSON]'s and [PERSON]'s algorithms can also been modified to obtain sub-optimal solutions for TSP. Class of _insertion algorithms_ were studied in [7]. They iteratively add new nodes to the current path. The variant that adds a new node to either end of the existing path can be seen as modification of the [PERSON]'s algorithm where additions are allowed only to the ends of the path. Similarly, algorithm called _Kruskal-TSP_[8] modifies [PERSON]'s algorithm so that it allows to merge two spanning trees (paths in case of TSP) only by their end points. In this paper, we introduce a more sophisticated approach to utilize the minimum spanning tree to obtain solution for travelling salesman problem. The algorithm, called _MST-to-TSP_, creates a minimum spanning tree using any algorithm such as Prim or Kruskal. However, instead of adding redundant links like Christofides, we detect branching nodes and eliminate them by a series of link swaps, see Figure 2. _Branching node_ is a node that connects more than two other nodes in the tree [6]. We introduce two strategies. First, a simple _greedy_ variant removes the longest of all links connecting to any of the branching nodes.