Computing Tree-Depth Faster Than \(2^{n}\)
A connected graph has tree-depth at most \(k\) if it is a subgraph of the closure of a rooted tree whose height is at most \(k\). We give an algorithm which for a given \(n\)-vertex graph \(G\), in time \({\mathcal {O}^*}(1.9602^n)\) computes the tree-depth of \(G\). Our algorithm is based on combinatorial results revealing the structure of minimal rooted trees whose closures contain \(G\).
tree-depth exact algorithms \(2^{n}\) barrier