Nick Brettell

activity

20152020

collaborators

7 papers

cs.DS2020

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1

The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O (tw)} n^{O (1)}$ , for F…

cs.DS2020

Colouring $(s P_{1} + P_{5})$ -Free Graphs: a Mim-Width Perspective

Nick Brettell, Jake Horsfield, Daniel Paulusma

We prove that the class of $(K_{t}, s P_{1} + P_{5})$ -free graphs has bounded mim-width for every $s \geq 0$ and $t \geq 1$ , and that there is a polynomial-time algorithm that, given a graph i…

cs.DS2020

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective

Hans Bodlaender, Nick Brettell, Matthew Johnson +3

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced…

math.CO2018

$N$ -detachable pairs in 3-connected matroids II: life in $X$

Nick Brettell, Geoff Whittle, Alan Williams

Let $M$ be a 3-connected matroid, and let $N$ be a 3-connected minor of $M$ . A pair ${x_{1}, x_{2}} \subseteq E (M)$ is $N$ -detachable if one of the matroids $M / x_{1} / x_{2}$ or $M \backsla…

math.CO2018

$N$ -detachable pairs in 3-connected matroids I: unveiling $X$

Nick Brettell, Geoff Whittle, Alan Williams

Let $M$ be a 3-connected matroid, and let $N$ be a 3-connected minor of $M$ . We say that a pair ${x_{1}, x_{2}} \subseteq E (M)$ is $N$ -detachable if one of the matroids $M / x_{1} / x_{2}$ or…

cs.DS2016

Parameterized vertex deletion problems for hereditary graph classes with a block property

Édouard Bonnet, Nick Brettell, O-joung Kwon +1

For a class of graphs $P$ , the Bounded $P$ -Block Vertex Deletion problem asks, given a graph $G$ on $n$ vertices and positive integers $k$ and $d$ , whether ther…

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

Colouring (sP1​+P5​)-Free Graphs: a Mim-Width Perspective

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective

N-detachable pairs in 3-connected matroids II: life in X

N-detachable pairs in 3-connected matroids I: unveiling X

Parameterized vertex deletion problems for hereditary graph classes with a block property

Colouring $(s P_{1} + P_{5})$ -Free Graphs: a Mim-Width Perspective

$N$ -detachable pairs in 3-connected matroids II: life in $X$

$N$ -detachable pairs in 3-connected matroids I: unveiling $X$