Approximating clique-width and branch-width

Abstract. We construct a polynomial-time algorithm to approximate the branch-width of certain symmetric submodular functions, and give two applications. The first is to graph “clique-width”. Clique-width is a measure of the difficulty of decom-posing a graph in a kind of tree-structure, and if a graph has clique-width at most k then the corresponding decomposition of the graph is called a “k-expression”. We find (for fixed k) an O(n9 log n)-time algorithm that, with input an n-vertex graph, outputs either a (23k+2 − 1)-expression for the graph, or a true statement that the graph has clique-width at least k + 1. (The best earlier algorithm algorithm, by Johansson [13], constructed a 2k log n-expression for graphs of clique-width at most k.) It was already known that several graph problems, NP-hard on general graphs, are solvable in polynomial time if the input graph comes equipped with a k-expression (for fixed k). As a consequence of our algorithm, the same conclusion follows under the weaker hypothesis that the input graph has clique-width at most k (thus, we no longer need to be provided with an explicit k-expression). Another application is to the area of matroid branch-width. For fixed k, we find an O(n4)-time algorithm that, with input an n-element matroid in terms of its rank oracle, either outputs a branch-decomposition of width at most 3k − 1 or a true statement that the ma-troid has branch-width at least k + 1. The previous algorithm by Hliněny ́ [11] was only for representable matroids. 1