OP-0035OpenAlgorithms and data structures

Beating 2^n for the travelling salesman problem

Held–Karp has stood since 1962. No exact algorithm is known with running time O(1.99^n).

MSC 68W · Algorithms in computer science

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Is there an algorithm solving the travelling salesman problem exactly on $n$ cities with arbitrary non-negative weights in time $O(c^n)$ for some constant $c < 2$ ?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

The Held–Karp dynamic program runs in $O(2^n n^2)$ time and $O(2^n n)$ space. Six decades later the exponential base has not been improved in the general weighted case, making this one of the cleanest stagnation points in exact algorithms.

Known partial results

For the unweighted Hamiltonicity problem, Björklund (2010) gave an $O(1.657^n)$ randomised algorithm for undirected graphs, so the barrier is specific to weights.
Bounded-degree and bounded-treewidth cases admit faster algorithms.
Under the Strong Exponential Time Hypothesis, some related covering problems provably cannot be improved — but no such conditional lower bound is known for TSP itself.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.