A 1962 BARRIER FALLS IN COMPUTER SCIENCE

A Hamiltonian cycle is a round trip through a network that visits every point exactly once and returns to the start. In a directed network, each link is an arrow that can be followed only one way, like a one-way street. The weighted version of this problem is the asymmetric travelling salesman problem.

Deciding whether such a cycle exists is a textbook hard problem. In 1962, Richard Bellman and, independently, Michael Held and Richard Karp gave dynamic-programming algorithms that solve it in time about 2ⁿ for a network of n points (up to factors that grow only polynomially). For more than sixty years, nobody could do fundamentally better on general directed networks.

The undirected cousin had already fallen

For networks with two-way links, Andreas Björklund broke the barrier in 2014 with a randomised algorithm running in 1.657ⁿ, work that earned him the 2016 EATCS–IPEC Nerode Prize, according to the paper. It is still the fastest known for general undirected networks. For directed ones, progress came only for special cases — bipartite networks, networks with few links per point — or under an unproven hypothesis, Strassen’s asymptotic rank conjecture.

The new bound

Tomohiro Koana, of the University of Tokyo, and Soh Kumabe, of the Tokyo company CyberAgent, now give a randomised algorithm that decides the directed problem in time

O((375/196)ⁿ) = O(1.9133ⁿ)**.

For general directed networks, it is the first improvement in the base of the exponential since 1962.

Counting in odd and even

The difficulty is subtle. Counting cycles modulo 2 — knowing only whether their number is odd or even — was already possible below 2ⁿ. But an even, non-zero number of cycles looks exactly like zero. The classic fix is to give links random weights so that, at some total weight, a solution becomes unique (the isolation lemma); but the fast parity-counting method could not handle weights.

The authors’ recipe, in plain words:

1. Guess one arrow of the cycle, and look instead for a path through every point from one end of that arrow to the other.
2. Delete each arrow at random with probability 1/50.
3. At each point, create three groups of incoming arrows, and copy each surviving arrow into a random non-empty set of groups.
4. If a tour exists, then with probability at least (49/50)ⁿ⁻¹ one can pick one group per point so that the number of valid paths is odd.
5. Give each group — not each arrow — a random weight. Now the isolation trick works, and about (50/49)ⁿ repetitions suffice.
6. Each repetition computes the odd-or-even counts at every total weight in time (15/8)ⁿ, using sums of matrix determinants due to Björklund, Kaski and Koutis and a random “linearisation” also used by Arvind and Guruswami.

Multiply the two: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ.

A proof generated by a machine

The paper ends with a declaration on generative AI: ChatGPT 6 Astra generated the proof of the main theorem and helped draft the manuscript. The authors supplied the statements of the intermediate propositions, which give a combinatorial reading of the model’s original solution, then verified and revised everything and take full responsibility.

The result is theoretical — no program was run — and the algorithm is randomised, with a small chance of error either way. Between 1.9133 for one-way streets and 1.657 for two-way ones, a wide gap remains open.