Improved self-reduction algorithms for graphs with bounded treewidth. (English) Zbl 0768.68033

Bodlaender, Hans L.

Graph-theoretic concepts in computer science, Proc. 15th Int. Workshop, WG ’89, Castle Rolduc/Neth. 1989, Lect. Notes Comput. Sci. 411, 232-244 (1990).

Summary: [For the entire collection see Zbl 0759.00013.]
Recent results of N. Robertson and P. Seymour show, that every class that is closed under taking of minors can be recognized in \(O(n^ 3)\) time. If there is a fixed upper bound on the treewidth of the graphs in the class, i.e. if there is a planar graph not in the class, then the class can be recognized in \(O(n^ 2)\) time. However, this result is non- constructive in two ways: the algorithm only decides on membership, but does not construct ‘a solution’, e.g. a linear ordering, decomposition or embedding; and no method is given to find the algorithms. In many cases, both non-constructive elements can be avoided, using techniques of Fellows and Langston, based on self-reduction. In this paper we introduce two techniques that help to reduce the running time of sel-reduction algorithms. With help of these techniques we show that there exist \(O(n^ 2)\) algorithms, that decide on membership and construct solutions for treewidth, pathwidth, search number, vertex search number, node search number, cutwidth, modified cutwidth, vertex separation number, gate matrix layout, and progressive black-white pebbling, where in each case the parameter \(k\) is a fixed constant.

MSC:

68Q25	Analysis of algorithms and problem complexity
68R10	Graph theory (including graph drawing) in computer science
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85	Graph algorithms (graph-theoretic aspects)

Keywords:

search number; minor test; upper bound; treewidth; planar graph; self- reduction; pathwidth; vertex search number; node search number; cutwidth; vertex separation number; gate matrix layout; black- white pebbling

Citations:

Zbl 0759.00013