Why is the Traveling Salesman Problem considered hard?

It's NP-hard, meaning no known algorithm can solve every instance exactly in time that scales polynomially with the number of cities. The number of possible tours grows factorially, so exact brute-force solutions quickly become computationally infeasible as the city count grows.

What is the Held-Karp algorithm?

Held-Karp is a dynamic programming algorithm that solves TSP exactly in O(n²·2ⁿ) time using bitmasks to track visited city subsets — much faster than brute-force factorial enumeration, but still exponential and impractical for more than roughly 20-25 cities.

How is TSP solved in practice for real-world routing problems?

Real-world applications almost always use heuristic or approximation algorithms — such as nearest-neighbor construction followed by 2-opt or Lin-Kernighan local search — that find near-optimal tours quickly rather than guaranteeing the true optimum.

What does the Christofides algorithm guarantee?

For metric TSP, where distances satisfy the triangle inequality, the Christofides algorithm guarantees a tour no worse than 1.5 times the length of the optimal tour, and runs in polynomial time.

Is TSP related to the P vs NP problem?

Yes. TSP's decision variant is NP-complete, meaning a polynomial-time algorithm for it would imply P equals NP. Since no such algorithm is known despite decades of research, TSP is often cited as a concrete example of the practical stakes behind the P vs NP question.

Computer Science

Traveling Salesman Problem

A classic optimization problem for finding the shortest possible route visiting a set of cities exactly once

AdvancedConcept12.4K learners

The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits a given set of cities exactly once each and returns to the starting city, and it is one of the most famous NP-hard problems in computer science.

#TravelingSalesmanProblem #ComputerScience#Concept#Advanced#MinimumSpanningTree #KnapsackProblem #MasterTheorem #SoftwareEngineering#Glossary#SkillVeris

Definition

Overview

TSP is deceptively easy to state and famously hard to solve exactly at scale: given n cities and the distances between every pair, find the minimum-length tour that visits each city exactly once before returning home. The number of possible tours grows factorially with the number of cities — (n-1)!/2 for a symmetric distance matrix — so brute-force enumeration becomes computationally infeasible well before n reaches even a few dozen cities, despite the problem's simple phrasing. Exact algorithms exist that do better than brute force. The Held-Karp dynamic programming algorithm solves TSP exactly in O(n²·2ⁿ) time by using bitmasks to represent subsets of visited cities, a substantial improvement over factorial growth but still exponential and impractical beyond roughly 20-25 cities. Because TSP is NP-hard — and its decision-problem variant is NP-complete — no known algorithm solves it exactly in polynomial time, and it's widely believed (though not proven) that none exists, tying TSP directly to the P vs NP question that remains one of the most important open problems in theoretical computer science. Because exact solutions don't scale, practical applications almost always rely on approximation and heuristic algorithms that find a good, though not guaranteed optimal, tour quickly. Nearest-neighbor and greedy-edge constructions build a reasonable tour fast; 2-opt and Lin-Kernighan local search algorithms then iteratively improve an existing tour by swapping edges; and for the metric TSP variant (where distances satisfy the triangle inequality), the Christofides algorithm guarantees a tour within 1.5 times the optimal length. TSP and its variants underpin real-world logistics and routing problems — vehicle routing for delivery fleets, PCB drilling paths in circuit board manufacturing, DNA sequencing assembly, and network design — making it one of the rare purely theoretical hard problems that shows up constantly in industrial optimization software.

Key Concepts

Finds the shortest tour visiting every city exactly once and returning to start
Number of possible tours grows factorially, making brute force infeasible at scale
NP-hard problem; its decision variant is NP-complete
Held-Karp dynamic programming solves it exactly in O(n²·2ⁿ) time
No known polynomial-time exact algorithm exists
Heuristics (nearest neighbor, 2-opt, Lin-Kernighan) find good approximate solutions fast
Christofides algorithm guarantees a 1.5x-optimal tour for metric TSP
Directly connected to the unresolved P vs NP question

Use Cases

Vehicle routing optimization for delivery and logistics fleets

PCB drilling path optimization in circuit board manufacturing

DNA sequence assembly and fragment ordering in bioinformatics

Network and circuit design requiring minimal total wiring or routing cost

Warehouse and robotics path planning for picking or inspection routes

Benchmarking approximation algorithms and heuristic optimization techniques

Frequently Asked Questions

From the Blog

Learn Through Hobbies

Learn Algorithms Through Chess Puzzles

Chess is a perfect algorithmic playground: the knight's tour teaches BFS, the N- Queens problem teaches backtracking, move generation teaches recursion, and game AI teaches minimax search. This guide covers four classic computer science algorithms using chess problems that make the concepts tangible.