Efficient and constructive algorithms for the pathwidth and treewidth of graphs

Abstract

In this paper we give, for all constants k, l , explicit algorithms, that given a graph G = (V, E) with a tree-decomposition of G with treewidth at most l, 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 l. This result can be combined with a result of Reed [37], 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, Bodlaender [13] 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 ≤ k, computes the pathwidth of G and a path-decomposition of G of minimum width.