Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

✍ Scribed by Hans L. Bodlaender; Ton Kloks

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 373 KB
• Volume: 21
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0049

✦ Synopsis

In this paper we give, for all constants k, l, explicit algorithms that, given a graph Ž . Gs 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 w be combined with a result of B. Reed in ''Proceedings of the 24th Annual x Symposium on Theory of Computing,'' pp. 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-Ž . w decomposition of width at most k k constant . Also, H. L. Bodlaender in ''Proceedings of the 25th Annual Symposium on Theory of Computing,'' pp.

x 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 s V, E with treewidth F k, computes the pathwidth of G and a path-decomposition of G of minimum width. ᮊ 1996 Academic Press, Inc.

* A preliminary version of this paper appeared as ''Better algorithms for the pathwidth and treewidth of graphs,'' in the proceedings of ICALP'91.