Efficient and constructive algorithms for the pathwidth and treewidth of graphs. (English) Zbl 0861.68036

Bodlaender, Hans L.; Kloks, Ton

J. Algorithms 21, No. 2, 358-402 (1996).

Summary: We give, for all constants \(k\), \(\ell\), explicit algorithms that, given a graph \(G=(V,E)\) with a tree-decomposition of \(G\) with treewidth at most \(\ell\), decide whether the treewidth (or pathwidth) of \(G\) is at most \(k\), and, if so, find a tree-decomposition (or path-decomposition) of \(G\) of width at most \(k\), and that use \(O(|V|)\) time. In contrast with previous solutions, our algorithms do not rely on non-constructive reasoning and are single exponential in \(k\) and \(\ell\). This result can be combined with a result of B. Reed [in “Proceedings of the 24th Annual Symposium on Theory of Computing”, 221-228 (1992)], yielding explicit \(O(n\log n)\) algorithms for the problem, given a graph \(G\), to determine whether the treewidth (or pathwidth) of \(G\) is at most \(k\), and, if so, to find a tree- (or path-) decomposition of width at most \(k\) (\(k\) constant). Also, the author [in “Proceedings of the 25th Annual Symposium on Theory of Computing”, 226-234 (1993)] has used the result of this paper to obtain linear time algorithms for these problems. We also show that for all constants \(k\), there exists a polynomial time algorithm that, when given a graph \(G=(V,E)\) with treewidth \(\leq k\), computes the pathwidth of \(G\) and a path-decomposition of \(G\) of minimum width.

MSC:

68W10	Parallel algorithms in computer science
68R10	Graph theory (including graph drawing) in computer science

Keywords:

pathwidth