pith. sign in

arxiv: 2606.02492 · v1 · pith:2TKQJVTDnew · submitted 2026-06-01 · 💻 cs.CC · cs.DM· cs.DS

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
show 2 more authors
Frances Rosamond Ella Yates
This is my paper

Pith reviewed 2026-06-28 11:33 UTC · model grok-4.3

classification 💻 cs.CC cs.DMcs.DS
keywords Truly Linear FPTLinear FPTparameterized complexitydiagonalizationtreedepthBFS-widthlinear-time algorithmsSAT
0
0 comments X

The pith

Truly Linear FPT defined by O(n) + f(k) time is a strict subset of Linear FPT.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines Truly Linear FPT as the class of parameterized problems solvable in time O(n) plus a function of the parameter k. It proves via diagonalization that this class sits strictly inside Linear FPT, which allows a multiplicative O(n) factor times f(k). The work places multiple problems, including SAT, Vertex Cover, k-Path, and H-Coloring, inside TLFPT under parameterizations by solution size, treedepth, or BFS-width. These placements rely on linear-time search techniques that keep the n-dependence strictly additive. The distinction becomes relevant once input sizes grow large enough that any hidden linear factor in n is prohibitive.

Core claim

Truly Linear FPT consists exactly of those parameterized problems whose running time is O(n) + f(k). Diagonalization separates this class from Linear FPT by constructing a problem that lies in the latter but not the former. Concrete problems such as SAT, Vertex Cover, Min-Max Matching, (n-k)-Coloring, Diverse Pair of Matchings, k-Path, and H-Coloring belong to TLFPT when the parameter is solution size, treedepth, or BFS-width, with membership obtained through depth-first and breadth-first search methods that produce only additive dependence on n.

What carries the argument

The additive-versus-multiplicative distinction between O(n) + f(k) and O(n) * f(k), together with the diagonalization that witnesses a problem in the second class but not the first.

If this is right

  • SAT, Vertex Cover, and k-Path admit algorithms whose dependence on input size n is strictly additive once the parameter is fixed.
  • Treedepth and BFS-width serve as parameters that enable membership in TLFPT for problems whose classical parameterizations do not.
  • Linear-time data structures and search orders become the decisive tools for placing problems inside TLFPT.
  • For sufficiently large n, any algorithm outside TLFPT incurs an unavoidable multiplicative overhead linear in the input size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Other search-based parameters might be engineered to pull additional problems into TLFPT without changing their classical parameterizations.
  • The separation result suggests that similar additive/multiplicative distinctions could be drawn inside other parameterized classes beyond FPT.
  • Practical implementations for the listed problems must be examined to confirm that their hidden constants truly allow an additive rather than multiplicative dependence on n.

Load-bearing premise

The listed problems possess O(n) + f(k) algorithms under the chosen parameterizations by treedepth, BFS-width, or solution size.

What would settle it

An explicit algorithm for Vertex Cover (or any listed problem) whose worst-case time on instances of size n with fixed parameter value exceeds any O(n) + f(k) bound for every choice of f.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper defines Truly Linear FPT (TLFPT) as parameterized problems solvable in O(n) + f(k) time. It claims via diagonalization that TLFPT is a strict subset of Linear FPT (LFPT = O(n) · f(k)). It asserts membership in TLFPT for SAT, Vertex Cover, Min-Max Matching, (n-k)-Coloring, Diverse Pair of Matchings, k-Path, and H-Coloring under parameterizations including solution size, treedepth, and BFS-width, using depth- and breadth-first search techniques.

Significance. If the diagonalization and the O(n)+f(k) memberships hold, the distinction between additive and multiplicative linear dependence on n would be a meaningful refinement of FPT for big-data regimes. The suggestion that treedepth and BFS-width are natural for the additive-linear setting could be useful if supported by concrete algorithms.

major comments (2)
  1. [Abstract] Abstract: the assertion that TLFPT is a strict subset of LFPT 'via diagonalization' is stated without any construction, proof sketch, or section reference that would allow verification of the separation.
  2. [Abstract] Abstract: the claim that SAT, Vertex Cover, k-Path, H-Coloring and the other listed problems belong to TLFPT under treedepth, BFS-width or solution-size parameterizations requires explicit algorithms or reductions establishing an O(n)+f(k) bound; none are supplied.
minor comments (1)
  1. The abstract refers to 'techniques based on depth- and breadth-first search' without indicating the section(s) in which these techniques are developed or applied to the listed problems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed comments. We respond to each major comment below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion that TLFPT is a strict subset of LFPT 'via diagonalization' is stated without any construction, proof sketch, or section reference that would allow verification of the separation.

    Authors: The diagonalization establishing the strict inclusion TLFPT ⊂ LFPT appears in full in Section 3, including the explicit construction. We will revise the abstract to add a direct reference to Section 3. revision: yes

  2. Referee: [Abstract] Abstract: the claim that SAT, Vertex Cover, k-Path, H-Coloring and the other listed problems belong to TLFPT under treedepth, BFS-width or solution-size parameterizations requires explicit algorithms or reductions establishing an O(n)+f(k) bound; none are supplied.

    Authors: The O(n)+f(k) algorithms and reductions for SAT, Vertex Cover, Min-Max Matching, (n-k)-Coloring, Diverse Pair of Matchings, k-Path, and H-Coloring (under the stated parameters) are given in Sections 4-7. We will revise the abstract to include section references to these results. revision: yes

Circularity Check

0 steps flagged

No circularity: new definition and diagonalization are independent of inputs

full rationale

The paper defines TLFPT as O(n)+f(k) and LFPT as O(n)·f(k), then invokes diagonalization to prove strict inclusion. This is a standard hierarchy argument that does not reduce to any fitted parameter or self-referential equation. Membership claims for SAT, Vertex Cover, k-Path etc. are asserted under treedepth/BFS-width/solution-size but are not derived from prior results by the same authors; they are external algorithmic statements whose verification lies outside the derivation chain. No self-citation is load-bearing, no ansatz is smuggled, and no renaming of known results occurs. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the existence of O(n)+f(k) algorithms for the enumerated problems under the stated parameters and on the correctness of an unspecified diagonalization construction; none of these are evidenced in the abstract.

axioms (1)
  • domain assumption A diagonalization argument separates the additive O(n)+f(k) class from the multiplicative O(n)·f(k) class.
    The abstract invokes this argument to establish strict inclusion but provides no further detail.

pith-pipeline@v0.9.1-grok · 5926 in / 1507 out tokens · 34160 ms · 2026-06-28T11:33:37.241757+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

  1. [1]

    Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications

    1 René van Bevern. Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications. PhD thesis, Universitätsverlag der TU, Berlin, 10 2014.doi:10.14279/depositonce-4131. 2 Hans L. Bodlaender. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM Journal on Computing, 25(6):1305...

    work page doi:10.14279/depositonce-4131 2014

  2. [2]

    URL:https://epubs.siam.org/doi/10.1137/ S0097539793251219,doi:10.1137/S0097539793251219

    Publisher: Soci- ety for Industrial and Applied Mathematics. URL:https://epubs.siam.org/doi/10.1137/ S0097539793251219,doi:10.1137/S0097539793251219. 3 Jonathan F Buss and Judy Goldsmith. Nondeterminism within P∗. SIAM Journal on Computing, 22(3):560–572,

    work page doi:10.1137/s0097539793251219

  3. [3]

    5 Jianer Chen, Iyad A

    URL:https: //cds.cern.ch/record/2931994,doi:10.17181/AnnualReport2024. 5 Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40):3736–3756,

    work page doi:10.17181/annualreport2024

  4. [4]

    com/science/article/pii/S0304397510003609,doi:10.1016/j.tcs.2010.06.026

    URL:https://www.sciencedirect. com/science/article/pii/S0304397510003609,doi:10.1016/j.tcs.2010.06.026. 6 Stephen A. Cook and Robert A. Reckhow. Time bounded random access machines.Journal of Computer and System Sciences, 7(4):354–375,

    work page doi:10.1016/j.tcs.2010.06.026 2010

  5. [5]

    com/science/article/pii/S0022000073800297,doi:10.1016/S0022-0000(73)80029-7

    URL:https://www.sciencedirect. com/science/article/pii/S0022000073800297,doi:10.1016/S0022-0000(73)80029-7. 7 Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.Introduction to algorithms (3rd ed.). MIT press,

    work page doi:10.1016/s0022-0000(73)80029-7

  6. [6]

    9 Rod G Downey and Michael R Fellows

    doi:10.1007/978-3-319-21275-3. 9 Rod G Downey and Michael R Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24(4):873–921,

    work page doi:10.1007/978-3-319-21275-3

  7. [7]

    Springer Science & Business Media, 1999.doi:10.1007/978-1-4612-0515-9

    11 Rodney G Downey and Michael Ralph Fellows.Parameterized complexity. Springer Science & Business Media, 1999.doi:10.1007/978-1-4612-0515-9. 12 Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs.J. ACM, 60(5), October 2013.doi:10.1145/2499483. 13 David Eppstein, Michael T. Goodrich, and Songyu Liu...

    work page doi:10.1007/978-1-4612-0515-9 1999

  8. [8]

    14 Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow

    URL:https://arxiv.org/ abs/2505.10789,arXiv:2505.10789. 14 Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow. Smoothing the Gap Between NP and ER.SIAM Journal on Computing, 53(6):FOCS20–102–FOCS20–138, 2024.arXiv:https: //doi.org/10.1137/20M1385287,doi:10.1137/20M1385287. 15 Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theore...

    work page doi:10.1137/20m1385287 2024

  9. [9]

    1007/s00453-024-01214-7,doi:10.1007/S00453-024-01214-7

    URL:https://doi.org/10. 1007/s00453-024-01214-7,doi:10.1007/S00453-024-01214-7. 17 John Franco and Allen Van Gelder. A perspective on certain polynomial-time solvable classes of satisfiability.Discrete Applied Mathematics, 125(2-3):177–214,

    work page doi:10.1007/s00453-024-01214-7

  10. [10]

    Association for Computing Machinery.doi:10.1145/100216.100217. 19 M.L. Fredman and D.E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. InProceedings

    work page doi:10.1145/100216.100217

  11. [11]

    Bumpus, Downey, Eagling-Vose, Enright, Fellows, Kutner, Larios-Jones, Martin, Rosamond, andYates XX:41 20 Michael R Garey and David S Johnson.Computers and intractability, volume

    31st Annual Symposium on Foundations of Computer Science, pages 719–725 vol.2, 1990.doi:10.1109/FSCS.1990.89594. Bumpus, Downey, Eagling-Vose, Enright, Fellows, Kutner, Larios-Jones, Martin, Rosamond, andYates XX:41 20 Michael R Garey and David S Johnson.Computers and intractability, volume

    work page doi:10.1109/fscs.1990.89594 1990

  12. [12]

    2017.05.017

    URL:https://doi.org/10.1016/j.tcs.2017.05.017, doi:10.1016/J.TCS. 2017.05.017. 22 Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert E. Tarjan, and Jakub Tet˘ ek. Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2099–2130,

    work page doi:10.1016/j.tcs.2017.05.017 2017

  13. [13]

    Ridgeless

    doi: 10.1109/FOCS61266.2024.00125. 23 Torben Hagerup. Sorting and searching on the word RAM. In Michel Morvan, Christoph Meinel, and Daniel Krob, editors,STACS98, pages 366–398, Berlin, Heidelberg,

    work page doi:10.1109/focs61266.2024.00125 2024

  14. [14]

    24 Anne-Sophie Himmel, George B

    Springer Berlin Heidelberg. 24 Anne-Sophie Himmel, George B. Mertzios, André Nichterlein, and Rolf Niedermeier. Fast parameterized preprocessing for polynomial-time solvable graph problems.Commun. ACM, 67(4):70–79, March 2024.doi:10.1145/3624713. 25 Bart Jansen. Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights. In Tiziana Calamone...

    work page doi:10.1145/3624713 2024

  15. [15]

    27 Richard M

    URL:https://www.sciencedirect.com/ science/article/pii/S0166218X15002218,doi:10.1016/j.dam.2015.04.028. 27 Richard M. Karp. Reducibility Among Combinatorial Problems. In Raymond E. Miller and James W. Thatcher, editors,Complexity of Computer Computations, pages 85–103. Plenum Press, New York,

    work page doi:10.1016/j.dam.2015.04.028 2015

  16. [16]

    dagstuhl.de/entities/document/10.4230/DagRep.13.8.1,doi:10.4230/DagRep.13.8.1

    URL:https://drops. dagstuhl.de/entities/document/10.4230/DagRep.13.8.1,doi:10.4230/DagRep.13.8.1. 29 Tomohiro Koana, Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zs- choche. Data reduction for maximum matching on real-world graphs: Theory and experiments. Journal of Experimental Algorithmics (JEA), 26:1–30,

    work page doi:10.4230/dagrep.13.8.1

  17. [17]

    31 Wolfgang Mader

    doi:10.1145/3155299. 31 Wolfgang Mader. Homomorphism properties and average edge density of graphs.Mathematical Annals, 174(4):265–268,

    work page doi:10.1145/3155299

  18. [18]

    34 Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz

    doi:10.1007/ s00453-020-00736-0. 34 Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz. Computing Treedepth in Polynomial Space and Linear FPT Time. In Shiri Chechik, Gonzalo Navarro, Eva Ro- tenberg, and Grzegorz Herman, editors,30th Annual European Symposium on Algorithms (ESA 2022), volume 244 ofLeibniz International Proceedings in Informatics (LI...

    2022

  19. [19]

    URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022

    Schloss Dagstuhl – Leibniz-Zentrum für Inform- XX:42O(n) +f(k): Truly Linear FPT atik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022. 79,doi:10.4230/LIPIcs.ESA.2022.79. 35 Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer,

    work page doi:10.4230/lipics.esa.2022 2022

  20. [20]

    36 Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar

    doi:10.1007/ 978-3-642-27875-4. 36 Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors,Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-...

    2014

  21. [21]

    37 Mihalis Yannakakis and Fanica Gavril

    doi:10.1007/978-3-662-43948-7\_77. 37 Mihalis Yannakakis and Fanica Gavril. Edge dominating sets in graphs.SIAM journal on applied mathematics, 38(3):364–372,

    work page doi:10.1007/978-3-662-43948-7