# zbMATH — the first resource for mathematics

Efficient and constructive algorithms for the pathwidth and treewidth of graphs. (English) Zbl 0861.68036
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
pathwidth
Full Text: