Barnaby Martin

activity

20222026

collaborators

Showing 2026Show all

3 papers · 1 filter

cs.CC2026

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

Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose +7

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-…

math.CO2026

On Detecting $H$ -Induced Minors for Small $H$

Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma +1

We consider the $H$ -Induced Minor problem: for a fixed graph~ $H$ , decide whether a given graph $G$ contains $H$ as an induced minor. While the problem is known to be NP-complete fo…

math.CO2026

Steiner Forest for $H$ -Subgraph-Free Graphs

Tala Eagling-Vose, David C. Kutner, Felicia Lucke +4

Our main result is a full classification, for every connected graph $H$ , of the computational complexity of Steiner Forest on $H$ -subgraph-free graphs. To obtain this dichotomy, we…

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

On Detecting H-Induced Minors for Small H

Steiner Forest for H-Subgraph-Free Graphs

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

On Detecting $H$ -Induced Minors for Small $H$

Steiner Forest for $H$ -Subgraph-Free Graphs