Branch-width of connectivity functions is fixed-parameter tractable

Abstract

A connectivity function on a finite set $V$ is a symmetric submodular function $f:2^V\to \mathbb{Z}$ with $f(\varnothing )=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)}{\hat{I}}^3{n}^6\log n$, where ${\hat{I}}^3$ 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 ${\hat{I}}^3{n}^{O(k)}$. Our algorithm can be applied to rank-width of graphs, branch-width of matroids, branch-width of (hyper)graphs, and carving-width of graphs. This resolves an open problem asked by Hliněný [SIAM J. Comput., 2005], who asked whether branch-width of matroids given by the rank oracle is fixed-parameter tractable. Furthermore, our algorithm improves the best known dependency on $k$ in the running times of FPT algorithms for graph branch-width, rank-width, and carving-width.

13 pages; fixed typos in the proof (Prop. 2.4 and Prop. 6.3)