research
∙
01/02/2022
Classifying Subset Feedback Vertex Set for H-Free Graphs
In the Feedback Vertex Set problem, we aim to find a small set S of vert...
share
research
∙
05/06/2021
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
We prove new complexity results for Feedback Vertex Set and Even Cycle T...
research
∙
05/28/2020
Computing Subset Transversals in H-Free Graphs
We study the computational complexity of two well-known graph transversa...
research
∙
04/16/2020
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
We consider the classical problems (Edge) Steiner Tree and Vertex Steine...
research
∙
04/10/2020
Bounding the Mim-Width of Hereditary Graph Classes
A large number of NP-hard graph problems become polynomial-time solvable...
research
∙
10/11/2019
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Let vc(G), fvs(G) and oct(G), respectively, denote the size of a minimum...
research
∙
08/01/2019
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
A graph is H-free if it contains no induced subgraph isomorphic to H. We...
research
∙
12/22/2017