The traveling salesman problem (TSP) is one of the classic NP-Hard combinatorial optimization problems. Efficient heuristics for the TSP have been the focus in research of computer science at all times. As a new tool to describe the structure of the TSP, the fat is essential for heuristic algorithm design. Since research on the fat is still at the beginning stage, It still lacks theoretical results and related heuristic algorithms. In this paper Firstly, the fat computational complexity for the TSP is investigated. It’s proved that it is NP-Hard to obtain the fat of the TSP through construction of biased instances, i.e., there is no algorithm to get the full fat of the TSP in polynomial time on the assumption P?NP. Furthermore, a meta-heuristic——dynamic candidate set search (DCSS) was proposed by analysis of the relationship between local optimal solutions and the fat. And the DCSS was applied to the LKH, one of the best existing algorithms for the TSP to improve it. Extensively wide experimental results on typical instances from the benchmark—TSPLIB indicate that the improved algorithm has a better performance than the LKH in terms of solution quality. This new fat-based heuristic shows a new way for other NP-hard problems.