An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

摘要

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 k n 3) time algorithm for this problem, significantly improving the previous algorithm of time O(4k3n5)O(4^{k^{3}}n^{5}) for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n).