Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset

Given an undirected graph G, a collection \(s₁,t₁), , (sₖ,tₖ)\ 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ᵢ from the corresponding tᵢ. 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³)· nO(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)· nO(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.