TY - GEN
T1 - An O*(1.84k) parameterized algorithm for the multiterminal cut problem
AU - Cao, Yixin
AU - Chen, Jianer
AU - Fan, Jia Hao
PY - 2013/9/3
Y1 - 2013/9/3
N2 - 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. One is max volume min (s,t)-cuts by [Ford and Fulkerson, Flows in Networks. Princeton University Press, 1962], and the other is isolating cuts by [Dahlhaus et al., The complexity of multiterminal cuts. SIAM J. Comp. 23(4), 1994]. 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.84k·nO(1), thereby breaking the 2k·nO(1)barrier. As a by-product, it gives a 1.36k·nO(1)algorithm for 3-terminal cut. The preprocessing applied on non-terminal vertices might be of use for study of this problem from other aspects.
AB - 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. One is max volume min (s,t)-cuts by [Ford and Fulkerson, Flows in Networks. Princeton University Press, 1962], and the other is isolating cuts by [Dahlhaus et al., The complexity of multiterminal cuts. SIAM J. Comp. 23(4), 1994]. 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.84k·nO(1), thereby breaking the 2k·nO(1)barrier. As a by-product, it gives a 1.36k·nO(1)algorithm for 3-terminal cut. The preprocessing applied on non-terminal vertices might be of use for study of this problem from other aspects.
UR - http://www.scopus.com/inward/record.url?scp=84883174787&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40164-0_11
DO - 10.1007/978-3-642-40164-0_11
M3 - Conference article published in proceeding or book
SN - 9783642401633
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 84
EP - 94
BT - Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings
T2 - 19th International Symposium on Fundamentals of Computation Theory, FCT 2013
Y2 - 19 August 2013 through 21 August 2013
ER -