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

CREATORBenjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose, Jessica Enright, Michael R. Fellows, David C. Kutner, Laura Larios-Jones, Barnaby Martin, Frances Rosamond, Ella Yates
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE125 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.02492

Browse the full library · About the Tower of Babel