FPT algorithms for path‐transversal and cycle‐transversal problems

We study the parameterized complexity of several vertex‐ and edge‐deletion problems on graphs, parameterized by the number $p$ of deletions. The first kind of problems are separation problems on undirected graphs, where we aim at separating distinguished vertices in a graph. The second kind of problems are feedback set problems on group‐labelled graphs, where we aim at breaking nonnull cycles in a graph having its arcs labelled by elements of a group. We obtain new FPT algorithms for these different problems, relying on a generic $O^{*}\left(4^p\right)$ algorithm for breaking paths of a homogeneous path system.