An Oz.ast;(1.84k)parameterized algorithm for the multiterminal cut problem

Yixin Cao, Jianer Chen, J. H. Fan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

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.84k×nO(1)time, thereby breaking the 2k×nO(1)barrier. As a by-product, it gives a 1.36k×nO(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.
Original languageEnglish
Pages (from-to)167-173
Number of pages7
JournalInformation Processing Letters
Volume114
Issue number4
DOIs
Publication statusPublished - 1 Apr 2014
Externally publishedYes

Keywords

  • Graph algorithms
  • Parameterized computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this