<p>This paper <a href="https://arxiv.org/abs/2104.07463" rel="nofollow noreferrer">https://arxiv.org/abs/2104.07463</a> 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 <span class="math-container">$2^{O(k^3)} n$</span> time Algorithm of Bodlaender given in 1996 [1], and after that there has not been improvements on the dependency on <span class="math-container">$k$</span>, even if we would sacrifice the dependency on <span class="math-container">$n$</span> to some worse polynomial. I think improving this has been listed multiple times as an open problem, and there even exists this <a href="https://arxiv.org/abs/1905.03643" rel="nofollow noreferrer">https://arxiv.org/abs/1905.03643</a> 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.</p>
<p>For FPT computing of optimal branch decomposition, there is an algorithm of Bodlaender and Thilikos [2] which also has time complexity <span class="math-container">$2^{O(k^3)}n$</span>. It uses very similar techniques as the Bodlaender's algorithm for treewidth. Similarly as for treewidth, no FPT algorithms with better depency on <span class="math-container">$k$</span> are known.</p>
<p>[1] Bodlaender, Hans L. &quot;A linear-time algorithm for finding tree-decompositions of small treewidth.&quot; SIAM Journal on computing 25.6 (1996): 1305-1317.</p>
<p>[2] Bodlaender, Hans L., and Dimitrios M. Thilikos. &quot;Constructive linear time algorithms for branchwidth.&quot; International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 1997.</p>

CC BY-SA 4.0
2021-11-25T19:53:01.740Z
2021-11-25T19:53:01.740Z
Laakeri
<p>The algorithm in reference [29] of the mentioned table is also valid for the branch-width of graphs.</p>

CC BY-SA 4.0
2021-11-26T08:44:22.383Z
2021-11-26T08:44:22.383Z
M. kanté
<p>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)</p>
<p>Somewhat related, this <a href="https://arxiv.org/abs/2111.03492" rel="nofollow noreferrer">paper</a> from 2021 gives results for rankwidth, looking for equivalent for treewidth/branchwidth (also <a href="https://arxiv.org/abs/2104.07463" rel="nofollow noreferrer">this</a> for SOTA of treewidth 2-approximation). Any references appreciated!</p>
<p><a href="https://i.sstatic.net/gLmTe.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/gLmTe.png" alt="enter image description here" /></a></p>

<parameterized-complexity><treewidth>
Parameterized complexity of tree/branch decomposition
Yaroslav Bulatov
# Parameterized complexity of tree/branch decomposition

(Asked by: username_0 on 2021-11-25)

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](https://arxiv.org/abs/2111.03492) from 2021 gives results for rankwidth, looking for equivalent for treewidth/branchwidth (also [this](https://arxiv.org/abs/2104.07463) for SOTA of treewidth 2-approximation). Any references appreciated!

[![enter image description here](https://i.sstatic.net/gLmTe.png)](https://i.sstatic.net/gLmTe.png)

**Tags:** parameterized-complexity, treewidth


---

## 2 answers

### Answer by username_1 on 2021-11-25. Score: 4 | Accepted answer

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.


---

### Answer by username_2 on 2021-11-26. Score: 3

The algorithm in reference [29] of the mentioned table is also valid for the branch-width of graphs.


---

