Efficient FPT Approaches for Constrained TSP Using Minimum Clique Cover

In this paper, we present a Fixed-Parameter Tractable (FPT) solution for the well-known Traveling Salesman Problem (TSP). We propose a minimum vertex clique cover algorithm, constrained by a fixed parameter of 2 to 3 vertices. Our approach systematically applies recursive techniques to cover cliques of 2 or 3 vertices, ensuring that the minimal solution to the original decision problem is achieved. The developed technique yields a linear-time FPT solution based on the input number of vertices for a given weighted graph, where each edge e is assigned a non-negative weight w. The graph is composed of multiple subgraphs, and our method identifies the minimum weight subgraphs to efficiently solve the TSP using this vertex-based FPT approach. This framework provides a robust and scalable solution for addressing TSP in weighted graphs.