# Accelerate Incremental TSP Algorithms on Time Evolving Graphs with Partitioning Methods
## 1 Introduction  
A graph is a commonly used data structure used to represent data with relationships. In the real world, graphs are used in the transportation systems, biological networks, social media graphs, and so on. Time-evolving graphs (TEG) are the graphs that evolve with time. Generally, there can be the following update events on a graph: edge/vertex addition, deletion, and changes in weight. These update events change the structure of the TEG. Traditionally, these graphs are computed by building a set of graph snapshots of the data and applying the static graph techniques to them. However, the maintenance of graph snapshots is expensive when the volume and the velocity of update event increase and leads to wastage in terms of memory storage and computation power. Developing an efficient algorithm for TEG is a critical and, at the same time, a challenging task, too.  
The traveling salesman problem (TSP) computes the shortest tour originating from a source vertex in a given graph by visiting each vertex exactly once. Solving TSP [1] is time consuming as well as computationally expensive because it is a NP-hard problem [2]. TSP is a commonly seen graph problem that can be applicable to a variety of applications in the field of robotics [3], trajectory planning for electromagnetic docking [4, 5, 6], and operation research [7]. The TSP problem can be mapped to various real-life applications and leads to an extended version of TSP such as Clustered TSP [8], Generalized TSP [9, 10, 11], and Multiple TSP [12, 13]. Applying those algorithms to TEG leads to significant recomputation overhead whenever a graph change event occurs. Hence, traditional approaches will not be feasible on rapidly evolving graphs.  
In our previous work, we have addressed the challenge of TEG by proposing an incremental algorithm [14]. The proposed incremental algorithms (I-TSP and Ig-TSP) minimized the number of recomputations on the graph by only computing the affected part of the graph and maintained the TSP tour across time intervals. We have further reduced the computation time of the I-TSP and Ig-TSP algorithms by defining a partitioning method [15] on top if it. The proposed partitioning algorithms (P-TSP and Pg-TSP) partition the graph in sub-graphs and compute sub-tours independently on each sub-graph. Then, thesesub-tours are connected to form a tour through all the partitions. From our experimental results, we observed that the computation time can be significantly reduced for incremental algorithms (I-TSP and Ig-TSP) by using partitioning TSP algorithms (P-TSP and Pg-TSP), and the time reduction can be greater under a higher number of partitions.  
In this work, we have mapped our TSP problem to three partitioning methods named (1) Vertex size attribute-based partitioning, (2) Edge size attribute-based partitioning, and (3) k-means clustering-based partitioning. We have compared the result in terms of total computation time taken and the number of messages sent in computation. We have also examined the effect of increasing the number of partitions on the total computation time. Through our experiments, we have observed that the vertex size attribute performs the best because of the balanced number of vertices in each partition. Apart from experiments, we have provided the complexity analysis of the proposed algorithm in terms of number of messages and number of paths.  
The rest of the sections are structured as follows: Section 2 describes related works. The problem is defined in Section 3 along with the proposed algorithms. Section 4 discusses the complexity analysis. Section 5 presents the experiment results, and Section 6 concludes the paper.