4 papers · 1 filter
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 , for F…
Colouring -Free Graphs: a Mim-Width Perspective
Nick Brettell, Jake Horsfield, Daniel Paulusma
We prove that the class of -free graphs has bounded mim-width for every and , and that there is a polynomial-time algorithm that, given a graph i…
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…
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 , the Bounded -Block Vertex Deletion problem asks, given a graph on vertices and positive integers and , whether ther…