# Accelerate Incremental TSP Algorithms on Time Evolving Graphs with Partitioning Methods
## 4 Complexity Analysis  
In the TSP algorithm, the computation time depends on the number of vertices in graph. Even if the algorithm is executed in a distributed way, the number of messages sent to traverse all the permutations of TSP tours will be directly proportional to the number of vertices. In an incremental algorithm, the computation begins from the previous result. The previous result in our algorithm is the set of full-length paths traversed in the previous iteration. In order to measure time complexity, we measure how many less messages will be sent in an incremental algorithm. To calculate that, we will first show the number of messages for the distributed TSP algorithm, which is a distributed implementation of the TSP algorithm. The summary of previously proposed algorithms and the partitioning algorithm is shown in Table 2.  
\begin{table}
\begin{tabular}{l l l} \hline \hline
**Algorithm** & **Paths** & **Messages** \\ \hline Distributed-TSP (D-TSP) & \((n-1)!\) & \(n(n-1)!\) \\ \hline Incremental-TSP (I-TSP) & \(2/3*(n-1)!\) & \(2n/6(n-1)!\) \\ \hline Partitioning-TSP (P-TSP) & \((2/3*(n-1)!)/k\) & \((2n/6(n-1)!)/k\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Summary of complexity analysis.  
Figure 5: The partitioned graph after using the proposed partitioning methods (left to right): (1) Edge size attribute, (2) Node size attribute, (3) K-means method. Red-colored vertices belong to Partition 1 and blue-colored vertices belong to Partition 2.  
**Lemma 1**: _Number of paths P explored in distributed TSP algorithm is \((n-1)!\) and the total number of messages sent to compute those paths will be \(n(n-1)!\)._  
If we examine Figure 2, each vertex will send messages to all the neighbors in a complete graph. Since one vertex is marked as a source vertex, the total permuted paths possible will be \((n-1)!\). Now, to compute those \((n-1)!\) paths, messages will be sent in each superstep. The length of the path will be \(n+1\) because each path begins and ends in the source vertex. To compute the path of length \(n+1\), a total of n messages will be sent, which is equivalent to the number of edges in the path. Hence, the total number of messages sent will be \(n(n-1)!\)  
**Lemma 2**: _The number of paths P explored in the I-TSP algorithm is \(2/3*(n-1)!\), and the maximum total number of messages sent to compute those paths will be \(2n/6(n-1)!\)_  
From our experimental evaluation, we have observed that for any changed edge, the total affected paths will be \(2/3\) of the total number of permuted paths in the distributed TSP algorithm. Hence, the number of total permuted paths for I-TSP will be \(2/3*(n-1)!\). The number of messages sent to compute these affected paths depends on the location of changed edge in the path. If the changed edge occurs in the beginning of the path, the maximum number of messages sent will be \(n-1\), and if the changed edge is at the end of the path, the minimum number of messages sent will be \(1\). The average number of messages sent in the whole computation will be \(n/2\). Hence, the average number of messages sent to compute \(2/3*(n-1)!\) paths will be \(2n/6(n-1)!\).  
**Lemma 3**: _The number of paths explored in the P-TSP algorithm is \((2/3*(n-1)!)/k\) and the maximum total number of messages sent to compute those paths will be \((2n/6(n-1)!)/k\), where \(k\) is the number of partitions in the graph._  
For the P-TSP algorithm, the complexity depends on the number of partitions and the number of messages. Since the underlying algorithm for P-TSP is the I-TSP algorithm, the number of affected paths will be the total number of paths in I-TSP divided by the number of partitions. Similarly, the number of messages will be divided by the total number of partitions. Hence, the average number of messages sent to compute \((2/3*(n-1)!)/k\) paths will be \((2n/6(n-1)!)/k\).