An improved algorithm for finding tree decompositions of small width (Q4944974)

In [SIAM J. Comput. 25, No. 6, 1305-1317 (1996; Zbl 0864.68074)], for each constant \(k\), a linear time algorithm was given by H. L. Bodlaender, that given a graph \(G\), decides if \(G\) has treewidth at most \(k\), and if so, finds a tree decomposition of \(G\) of width at most \(k\). This paper gives a modification of that algorithm. The modification does in addition the following: when the input graph \(G\) has treewidth more than \(k\), then a subgraph \(G'\) of \(G\) is obtained, such that the treewidth of \(G'\) is between \(k+1\) and \(2k\); the output consists of \(G'\) and a tree decomposition of \(G'\) of width at most \(2k\). This modified algorithm can be used as a subroutine for an algorithm of the \(l\)-disjoint rooted paths problem. In this problem, \(l\) disjoint pairs of vertices are given, and the question is if there are mutually vertex-disjoint paths between every given pair. The result of this paper shows that this problem can be solved in \(O(n^2)\) time. For the entire collection see [Zbl 0929.00074].