{"id":"arxiv/2601.04756","url":"https://arxiv.org/abs/2601.04756","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Branch-width of connectivity functions is fixed-parameter tractable","domain":"cs.DS","source":"arxiv","authors":["Tuukka Korhonen","Sang-il Oum"],"reviews":0,"subject":"cs.DS","summary":"A connectivity function on a finite set $V$ is a symmetric submodular function $f \\colon 2^V \\to \\mathbb{Z}$ with $f(\\emptyset)=0$. We prove that finding a branch-decomposition of width at most $k$ for a connectivity function given by an oracle is fixed-parameter tractable (FPT), by providing an algorithm of running time $2^{O(k^2)} γn^6 \\log n$, where $γ$ is the time to compute $f(X)$ for any set $X$, and $n = |V|$. This improves the previous algorithm by Oum and Seymour [J. Combin. Theory Ser. B, 2007], which runs in time $γn^{O(k)}$. Our algorithm can be applied to rank-width of graphs,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-08","reactions":{}}