1 citations · 1 across the 3 of their papers we have counts for
6 papers · 1 filter
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…
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
A graph is -free if it contains no induced subgraph isomorphic to . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…
Finding a Small Number of Colourful Components
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin +3
A partition of the vertex set of a graph with a (not necessarily proper) colouring is colourful if no two vertices in any have the same colour and…
Independent Feedback Vertex Set for -free Graphs
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer , to delete at most vertices from a given graph so t…
Independent Feedback Vertex Sets for Graphs of Bounded Diameter
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets and , where is an independent set and induces…
Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity
Nina Chiarelli, Tatiana R. Hartinger, Matthew Johnson +2
We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Trans…