# Accelerate Incremental TSP Algorithms on Time Evolving Graphs with Partitioning Methods
## 3 Algorithms
### Graph Partitioning Algorithm  
The intuition of a partitioning algorithm is to localize the computation on a partition where an update event has occurred. Hence, recomputing a partial TSP tour on an affected partition instead of recomputing the whole graph will significantly reduce the computation time and the messages sent. After P-TSP/Pg-TSP computes a partial TSP tour on each partition, these tours are connected to obtain a full-length TSP tour. To implement this intuition, we have three main steps: (1) partition the graph, (2) recompute a partial TSP tour, and (3) connect the partial tours of each partition. The graph that will be used as reference is shown in Figure 3. The connecting process is shown in Figure 4. Finally the resultant graph for all partitioning strategies is shown in Figure 5.  
Step 1: Graph Partitioning: The input graph is partitioned to sub-graphs to reduce the communication cost in the distributed environment. In our problem definition, update event affects only one edge, and hence, the total computation time is reduced because recomputation will take place in at most one partition. A graph can be partitioned based on various constraints. We will discuss these constraints in detail in the next section.  
Step 2: Recompute TSP tour: Whenever an update event occurs, it will affect only two vertices of the partition. These two vertices can either be present in the same partition or in a different partition. If the affected vertices are in the same partition, then I-TSP or Ig-TSP will be used to compute the TSP tour on that partition. The recomputed tour is later connected with a partial tour of other partitions. If the vertices affected by the update event are in different partitions, we do not need to recompute at all and connect previously computed tours with a new minimum edge across partitions, which is explained in the next paragraph.  
Step 3: Connecting partial TSP tours: The changed edge will affect a maximum of two partitions of the graph. Therefore, the connecting process will also take place between two partitions. After step 2, we will have two recomputed partial tours of affected partitions. We propose an algorithm to connect n tours into one tour. The intuition of the algorithm is to cut each tour in a linear sequence and then connect them to construct a new tour. So, the first step is to find the cutting point, and the second step is to construct the tour. Figure 4 illustrates the connecting algorithm for a graph with two partitions.  
The pseudocode for both of our partitioning algorithms is shown in Algorithm 2. I-TSP and Ig-TSP are the underlying algorithms for partitioning algorithms. The propagation of I-TSP and Ig-TSP is shown in [14]. The input to the algorithm is an update event and a pathList from previous iterations. The graph is partitioned in line 1. If \(u\) and \(v\) of \(\Delta G_{t}(u,v,C(u,v))\) are present in the same partition (line 2), then depending on the mode, I-TSP (line 4) and Ig-TSP (line 6) are used to recompute the TSP tour on that partition. If both u and v are in different partitions, then the minimum edge is chosen (line 9) to connect the partitions (line 11).  
```
0:\(\Delta G_{t}(u,v,C(u,v))\), pathList.
0: A TSP tour, T
1:Partition the graph using edge attribute, node size attribute, or k-means method.
2:if u and v are in the same partition then
3:if mode == brute then
4: compute T using the I-TSP algorithm \(\triangleright\) P-TSP algorithm
5:else
6: compute T using the Ig-TSP algorithm \(\triangleright\) Pg-TSP algorithm
7:endif
8:else
9: Pick minimum weight edge across partitions CE(u',v').
10:endif
11:Connect tours of each partition by connecting CE(u',v').
```  
**Algorithm 2** Partitioned TSP Algorithms: P-TSP (Based on I-TSP) and Pg-TSP (Based on Ig-TSP).