Multiway $f$-Cut is fixed-parameter tractable

Abstract

A connectivity function on a finite set $E$ is a function $f:2^E\to \mathbb{Z}$ that is submodular and symmetric, with $f(\varnothing )=0$. Given a connectivity function $f$ via a value oracle, terminals $t_1,\dots ,t_r\in E$, and an integer $k$, the Multiway $f$-Cut problem asks whether $E$ has a partition $(P_1,\dots ,P_r)$ with $t_i\in P_i$ for every $i$ and ${\sum }_{i=1}^{r}f(P_i)\le k$. We prove that Multiway $f$-Cut is fixed-parameter tractable parameterized by $k$. Cut functions of graphs are connectivity functions, so as a special case we recover the classical result that Edge Multiway Cut in graphs is fixed-parameter tractable. Our proof of correctness is completely elementary, and is arguably the simplest known proof of this fact.

7 pages, 0 figures