An O(1.84k) parameterized algorithm for the multiterminal cut problem Academic Article uri icon

abstract

  • We study the multiterminal cut problem, which, given an n-vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such that each terminal is in a distinct part, and the total weight of crossing edges is at most k. Our weapons shall be two classical results known for decades: maximum volume minimum (s,t)-cuts by Ford and Fulkerson [11] and isolating cuts by Dahlhaus et al. [9]. We sharpen these old weapons with the help of submodular functions, and apply them to this problem, which enable us to design a more elaborated branching scheme on deciding whether a non-terminal vertex is with a terminal or not. This bounded search tree algorithm can be shown to run in 1.84knO(1) time, thereby breaking the 2knO(1) barrier. As a by-product, it gives a 1.36knO(1) time algorithm for 3-terminal cut. The preprocessing applied on non-terminal vertices might be of use for study of this problem from other aspects. 2013 Elsevier B.V.

published proceedings

  • Information Processing Letters

altmetric score

  • 0.75

author list (cited authors)

  • Cao, Y., Chen, J., & Fan, J.

citation count

  • 6

complete list of authors

  • Cao, Yixin||Chen, Jianer||Fan, J-H

publication date

  • April 2014