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(4~kn~(O(1))) time algorithm for this problem, significantly improving the previous algorithm of time O(4~(k~3) n~(O(1))) for the problem. Our result also gives the first polynomial time algorithm for the minimum node MULTIWAY CUT problem when the separator size is bounded by O(log n).