FIXED-PARAMETER TRACTABILITY OF MULTICUT PARAMETERIZED BY THE SIZE OF THE CUTSET

Given an undirected graph G, a collection {(s(1), t(1)),..., (s(k), t(k))} of pairs of vertices, and an integer p, the EDGE MULTICUT problem asks if there is a set S of at most p edges such that the removal of S disconnects every s(i) from the corresponding t(i). VERTEX MULTICUT is the analogous problem where S is a set of at most p vertices. Our main result is that both problems can be solved in time 2(O)(p(3))center dot n(O(1)), i.e., fixed-parameter tractable parameterized by the size p of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form f(p)center dot n(O(1)) exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.