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*(4(p)) algorithm for breaking paths of a homogeneous path system. (C) 2010 Elsevier B.V. All rights reserved.