$O(n +f(k))$: Truly Linear FPT
2026-06-01 • Computational Complexity
Computational ComplexityDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors discuss a concept called Truly Linear FPT (TLFPT), which focuses on algorithms whose running time is the sum of a function of a small parameter and a time linear in the input size, rather than multiplied. They show that TLFPT is a smaller, more restrictive class than previously studied linear FPT algorithms. Their work explores which problems fit into TLFPT using techniques like depth-first and breadth-first search, highlighting problems such as SAT and Vertex Cover. This approach aims to better handle extremely large data sets by ensuring algorithms scale more efficiently with input size.
Parameterized complexityFixed Parameter Tractability (FPT)Truly Linear FPT (TLFPT)Linear FPT (LFPT)NP-hard problemsParameterizationTreedepthBFS-widthDiagonalizationDepth-first search (DFS)
Authors
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
Abstract
Parameterized complexity has always been concerned with practical computing: by confining combinatorial explosion to a secondary parameter $k$, one can uncover why and how many NP-hard problems are effectively tackled in practice. Today, however, the scale of data has changed: scientists study Big Data, which is so large that even quadratic dependence in the total input size $n$ is unaffordable. Therefore, what constitutes a practical algorithm has also changed. Classically, parameterized complexity is blind to the difference between defining fixed parameter tractability multiplicatively (i.e. $f(k) \cdot n^c$) or additively (i.e. $f(k) + n^c$). But what if the constant $c$ is one and we require true linearity, is this distinction still inconsequential? Here, we define and explore Truly Linear FPT (TLFPT) -- that is $O(n)+f(k)$ -- and show that it is a strict subset of Linear FPT (LFPT) -- that is $O(n) \cdot f(k)$ -- via diagonalization. Populating TLFPT requires careful consideration of linear-time algorithmics and data structures. We meet many inhabitants of TLFPT: SAT, Vertex Cover, Min-Max Matching, $(n-k)$-Coloring, Diverse Pair of Matchings, $k$-Path, and $H$-Coloring. Our parameterizations are equally varied. Beyond classical parameters like solution size, we leverage two parameters, treedepth and BFS-width, which are particularly well-suited to the TLFPT regime. We do so by developing techniques based on depth- and breadth-first search. For parameterized complexity to be of service to the scientific community, we need to contend with Big Data. For sufficiently large inputs, FPT beyond linear may not suffice. Thus, there is a practical and theoretical need for more ambitious goals. TLFPT is a first step forward.