Search Results

Documents authored by Eagling-Vose, Tala


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}
}
Document
Optimal b-Colourings and Fall Colourings in H-Free Graphs

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniël Paulusma

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)


Abstract
In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in H-free graphs. For Tight b-Chromatic Number in H-free graphs, we develop a general technique to determine new graphs H, for which the problem is polynomial-time solvable, and we also determine new graphs H, for which the problem is still NP-complete. We show, for the first time, the existence of a graph H such that in H-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable.

Cite as

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniël Paulusma. Optimal b-Colourings and Fall Colourings in H-Free Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.WG.2026.2,
  author =	{Ahn, Jungho and Eagling-Vose, Tala and Lucke, Felicia and Manlove, David and Mendoza Granada, Fabricio and Paulusma, Dani\"{e}l},
  title =	{{Optimal b-Colourings and Fall Colourings in H-Free Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.2},
  URN =		{urn:nbn:de:0030-drops-261685},
  doi =		{10.4230/LIPIcs.WG.2026.2},
  annote =	{Keywords: b-chromatic number, tight graph, fall achromatic number, fall chromatic number, H-free graph}
}
Document
Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification

Authors: Tala Eagling-Vose, Jorik Jooken, Felicia Lucke, Barnaby Martin, and Daniël Paulusma

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)


Abstract
We consider Colouring on graphs that are H-subgraph-free for some fixed graph H, which are graphs that do not contain H as a subgraph. To classify the complexity of Colouring on H-subgraph-free graphs for connected H, it remains to consider when H is a tree of maximum degree 4 with exactly one vertex of degree 4, or a tree of maximum degree 3 with at least two vertices of degree 3. We let H be a so-called subdivided "H"-graph, which is either a subdivided ℍ₀: a tree of maximum degree 4 that is a star, or a subdivided ℍ₁: a tree of maximum degree 3 with exactly two vertices of degree 3. We develop new decomposition theorems resulting in polynomial-time algorithms, and in combination with known results, fully classify all cases ℍ₀ and ℍ₁. To illustrate the wider applicability of our techniques, we also employ them to obtain similar new polynomial-time results for two other classic graph problems: Stable Cut and, in part, Feedback Vertex Set.

Cite as

Tala Eagling-Vose, Jorik Jooken, Felicia Lucke, Barnaby Martin, and Daniël Paulusma. Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{eaglingvose_et_al:LIPIcs.WG.2026.16,
  author =	{Eagling-Vose, Tala and Jooken, Jorik and Lucke, Felicia and Martin, Barnaby and Paulusma, Dani\"{e}l},
  title =	{{Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.16},
  URN =		{urn:nbn:de:0030-drops-261827},
  doi =		{10.4230/LIPIcs.WG.2026.16},
  annote =	{Keywords: colouring, forbidden subgraph, complexity dichotomy}
}
Document
Finding d-Cuts in Claw-Free Graphs

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)


Abstract
The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets B and R such that the edges between B and R form a matching, that is, every vertex in B has at most one neighbour in R, and vice versa. If for some integer d ≥ 1, we allow every vertex in B to have at most d neighbours in R, and vice versa, we obtain the more general problem d-Cut. It is known that d-Cut is NP-complete for every d ≥ 1. However, for claw-free graphs, it is only known that d-Cut is polynomial-time solvable for d = 1 and NP-complete for d ≥ 3. We resolve the missing case d = 2 by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every d ≥ 2, d-Cut, restricted to claw-free graphs of maximum degree p, is constant-time solvable if p ≤ 2d+1 and NP-complete if p ≥ 2d+3. Moreover, in the former case, we can find a d-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to S_{1^t,𝓁}-free graphs where S_{1^t,𝓁} is the graph obtained from a star on t+2 vertices by subdividing one of its edges exactly 𝓁 times.

Cite as

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith. Finding d-Cuts in Claw-Free Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2025.4,
  author =	{Ahn, Jungho and Eagling-Vose, Tala and Lucke, Felicia and Paulusma, Dani\"{e}l and Smith, Siani},
  title =	{{Finding d-Cuts in Claw-Free Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.4},
  URN =		{urn:nbn:de:0030-drops-249121},
  doi =		{10.4230/LIPIcs.ISAAC.2025.4},
  annote =	{Keywords: matching cut, d-cut, claw-free, maximum degree}
}

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