Multiway $f$-Cut is fixed-parameter tractable
This provides a unified and simplified proof for a known result in graph algorithms, but its impact is limited to the theory of parameterized complexity for connectivity functions.
The paper proves that the Multiway f-Cut problem, a generalization of graph cut problems to arbitrary connectivity functions, is fixed-parameter tractable when parameterized by the cut size k. This generalizes the known fixed-parameter tractability of Edge Multiway Cut in graphs, and the proof is elementary and arguably simpler than previous proofs.
A connectivity function on a finite set $E$ is a function $f\colon 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,\ldots,t_r\in E$, and an integer $k$, the Multiway $f$-Cut problem asks whether $E$ has a partition $(P_1,\ldots,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.