O(n)+f(k): Truly Linear FPT

Jul 16, 2026

Parameterized complexity focuses on practical computation by isolating combinatorial blow-up into a secondary parameter k. With today’s Big Data, even quadratic dependence on the input size n can be prohibitive, changing what counts as a practically efficient algorithm. The work defines Truly Linear FPT (TLFPT) as O(n)+f(k) and proves via diagonalization that it forms a strict subset of Linear FPT (LFPT) defined as O(n)·f(k). It also develops techniques using treedepth and BFS-width and shows TLFPT inhabitants across numerous graph and combinatorial problems.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages42

Reading Time1 h 46 min

Introduction

Truly Linear FPT vs Linear FPT

Parameters and key techniques

Big Data motivation

arXiv :2606 .02492v 1 [ cs .CC] 1 Jun 2026 O (n) + f(k): Truly Linear FPT Benjamin Merlin Bumpus \# Instituto de Matemática e Estatística, Universidade de São Paulo. Rua do Matão, 1010— 05508–090, São Paulo, SP, Brasil. Rod Downey \# Victoria University of Wellington, School of Mathematics and Statistics, PO Box 600 Wellington, New Zealand Tala Eagling-Vose \# Department of Computer Science, Durham University, Durham, UK Jessica Enright \# School of Computing Science, University of Glasgow Michael R. Fellows \# Institute of Informatics, University of Bergen (Emeritus), Bergen, Norway David C. Kutner \# Department of Computer Science, Durham University, Durham, UK Laura Larios-Jones \# School of Computing Science, University of Glasgow, Glasgow, UK Barnaby Martin \# Department of Computer Science, Durham University, Durham, UK Frances Rosamond \# Institute of Informatics, University of Bergen (Emerita), Bergen, Norway Ella Yates \# School of Computing Science, University of Glasgow, Glasgow, UK ~~ 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 isunaffordable. 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) · nc ) or additively (i.e. f (k) + nc ) . 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) · 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. 2012 ACM Subject Classification Theory of computation → Fixed parameter tractability; Theory of computation → Complexity classes; Theory of computation → Parameterized complexity and exact algorithms; Mathematics of computing → Graph algorithms; Theory of computation → Dynamic programming; Theory of computation → Streaming, sublinear and near linear time algorithms © Benjamin Bumpus, Rod Downey, Tala Eagling-Vose, Jessica Enright, Michael R. Fellows, David C. Kutner, Laura Larios-Jones, Barnaby Martin, Frances Rosamond, and Ella Yates; licensed under Creative Commons License CC-BY 4.0 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany XX:2 O (n) + f(k): Truly Linear FPT Keywords and phrases Truly Linear FPT, fixed-parameter tractability, parameterized complexity, graph algorithms, kernelization, dynamic programming. Digital Object Identifier 10.4230/LIPIcs... Funding Jessica Enright: Partly supported by EPSRC grants EP/T004878/1 and EP/V032305/1 David C. Kutner: Partly supported by EPSRC grant EP/T004878/1, Multilayer Algorithmics to Leverage Graph Structure (MultilayerALGS) . Barnaby Martin:

FAQs

What is Truly Linear FPT (TLFPT) and how does it differ from Linear FPT (LFPT)?

TLFPT requires running time O(n)+f(k), while LFPT allows O(n)·f(k). The document proves TLFPT is a strict subset of LFPT using diagonalization.

Why is the motivation for TLFPT tied to Big Data?

With massive inputs, even dependence like n^2 becomes unaffordable, so practicality depends on near-linear dependence on n. The document argues that classical multiplicative vs additive distinctions are no longer sufficient at this scale.

Which graph problems and parameters are presented as fitting the TLFPT regime?

The work lists SAT, Vertex Cover, Min-Max Matching, (n−k)-Coloring, Diverse Pair of Matchings, k-Path, and H-Coloring. It uses parameters including treedepth and BFS-width and develops methods based on depth and breadth-first search.

Jul 16, 2026

Upload by Emma Wilson