I'm looking for an up to date reference for parameterized complexity of tree and branch decompositions. IE, complexity of finding tree/branch decomposition of optimal width in terms of relevant graph parameters (treewidth, branchwidth, graph size)
Somewhat related, this paper from 2021 gives results for rankwidth, looking for equivalent for treewidth/branchwidth (also this for SOTA of treewidth 2-approximation). Any references appreciated!
2 Answers 2
This paper https://arxiv.org/abs/2104.07463 gives an overview of treewidth algorithms in Table 1. Similar table also exists in Wikipedia. The situation for parameterized computing of an optimal tree decomposition is indeed as can be seen from these tables: The best exact FPT algorithm for treewidth is the 2ドル^{O(k^3)} n$ time Algorithm of Bodlaender given in 1996 [1], and after that there has not been improvements on the dependency on $k$, even if we would sacrifice the dependency on $n$ to some worse polynomial. I think improving this has been listed multiple times as an open problem, and there even exists this https://arxiv.org/abs/1905.03643 paper where an intermediate result towards improving the Bodlaender's algorithm is given, but ultimately without improving the time complexity. So people have definitely tried to improve this, but not succeeded.
For FPT computing of optimal branch decomposition, there is an algorithm of Bodlaender and Thilikos [2] which also has time complexity 2ドル^{O(k^3)}n$. It uses very similar techniques as the Bodlaender's algorithm for treewidth. Similarly as for treewidth, no FPT algorithms with better depency on $k$ are known.
[1] Bodlaender, Hans L. "A linear-time algorithm for finding tree-decompositions of small treewidth." SIAM Journal on computing 25.6 (1996): 1305-1317.
[2] Bodlaender, Hans L., and Dimitrios M. Thilikos. "Constructive linear time algorithms for branchwidth." International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 1997.
The algorithm in reference [29] of the mentioned table is also valid for the branch-width of graphs.