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

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.

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) |