{"id":"arxiv/2608.10380","url":"https://arxiv.org/abs/2608.10380","tags":["cs.DM","math.CO"],"score":0,"title":"Multiway $f$-Cut is fixed-parameter tractable","domain":"cs.DM","source":"arxiv","authors":["Tony Huynh","Eun Jung Kim","Sang-il Oum","Roohani Sharma","Marek Sokołowski"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}