Search Results

Documents authored by Yates, Ella


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

Authors: Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose, Jessica Enright, Michael R. Fellows, David C. Kutner, Laura Larios-Jones, Barnaby Martin, Frances Rosamond, and Ella Yates

Published in: LIPIcs, Volume 398, 21st International Symposium on Parameterized and Exact Computation (IPEC 2026)


Abstract
Parameterized complexity has always been concerned with practical computing: by confining combinatorial explosion to a secondary parameter k, one can uncover how NP-hard problems can be effectively tackled in practice. With the advent of big data, the scale of inputs have changed and modern data are often so large that even quadratic dependence in the total input size n is computationally unaffordable. What constitutes a practical algorithm has therefore also changed. Parameterized complexity has traditionally regarded the multiplicative (i.e. f(k)⋅n^{c_m}) and additive (i.e. f(k) + n^{c_a}) definitions of fixed-parameter tractability as interchangeable, even though the associated exponents c_m and c_a are constants whose values may be different. But if the constant c is 1 (that is, we must compute in time linear in the size of the input) - is this distinction still inconsequential? Here, we build on past work to describe and explore the complexity class Truly Linear FPT (TLFPT) - that is O(n)+f(k). We show that it is a strict subset of Linear FPT (LFPT) - that is O(n)⋅f(k) via diagonalization. Despite the restrictiveness of this class, we show that it contains a number of important problems: SAT, Vertex Cover, Min-Max Matching, (n-k)-Coloring, Diverse Pair of Matchings, k-Path, and H-Coloring. Showing that these problems are in TLFPT requires careful consideration of the details of data structures for instance manipulation and access, as is common in linear-time algorithmics. We use a number of different parameters for these problems, including both standard parameters like solution size, as well treedepth and BFS-width, which are particularly well-suited to the TLFPT regime due to their natural connection to depth- and breadth-first search, respectively.

Cite as

Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose, Jessica Enright, Michael R. Fellows, David C. Kutner, Laura Larios-Jones, Barnaby Martin, Frances Rosamond, and Ella Yates. O(n)+f(k): Truly Linear FPT. In 21st International Symposium on Parameterized and Exact Computation (IPEC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 398, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{bumpus_et_al:LIPIcs.IPEC.2026.22,
  author =	{Bumpus, Benjamin Merlin and Downey, Rod and Eagling-Vose, Tala and Enright, Jessica and Fellows, Michael R. and Kutner, David C. and Larios-Jones, Laura and Martin, Barnaby and Rosamond, Frances and Yates, Ella},
  title =	{{O(n)+f(k): Truly Linear FPT}},
  booktitle =	{21st International Symposium on Parameterized and Exact Computation (IPEC 2026)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-456-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{398},
  editor =	{Korhonen, Tuukka and Lampis, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2026.22},
  URN =		{urn:nbn:de:0030-drops-281956},
  doi =		{10.4230/LIPIcs.IPEC.2026.22},
  annote =	{Keywords: Truly Linear FPT, fixed-parameter tractability, parameterized complexity, graph algorithms, kernelization, dynamic programming}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail