O ( n ) + f ( k ) O(n)+f(k) : Truly Linear FPT
Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose, Jessica Enright, Michael R. Fellows, David C. Kutner, Laura Larios-Jones, Barnaby Martin, Frances Rosamond, Ella Yates · 2026
Read O ( n ) + f ( k ) O(n)+f(k) : Truly Linear FPT by Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose, Jessica Enright, Michael R. Fellows, David C. Kutner, Laura Larios-Jones, Barnaby Martin, Frances Rosamond, Ella Yates (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-02492.txt.
Description
Bumpus and co-authors define a stricter class of fast algorithms for hard problems. Parameterized complexity confines the explosion to a small parameter k. The input size n stays cheap in the classic view. Big Data changed that balance. Even a quadratic pass over n can cost too much. The classic view also hides a split. Multiplicative and additive forms of the cost bound look alike.
The new class is called Truly Linear FPT. Its cost is order n plus a function of k. The authors show it sits strictly inside Linear FPT. The proof uses diagonalization. Many known problems live in the new class. They include SAT, Vertex Cover, and k-Path. Diverse pairs of matchings and H-Coloring join the list. Two parameters, treedepth and BFS-width, suit this regime well. Depth-first and breadth-first techniques power the results.
Catalog record
| CREATOR | Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose, Jessica Enright, Michael R. Fellows, David C. Kutner, Laura Larios-Jones, Barnaby Martin, Frances Rosamond, Ella Yates |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 125 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.02492