Improved Self-Reduction Algorithms for Graphs with Bounded Treewidth

Recent results of Robertson and 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 self-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.