Testing branch-width

Abstract

An integer-valued function f on the set 2(V) of all subsets of a finite set V is a connectivity function if it satisfies the following conditions: (1) f (X) + f(Y) >= f (X n Y) + f (X u Y) for all subsets X, Y of V, (2) f (X) = f (V \ X) for all X subset of V, and (3) f (theta) = 0. Branch-width is defined for graphs, matroids, and more generally, connectivity functions. We show that for each constant k, there is a polynomial-time (in vertical bar V vertical bar) algorithm to decide whether the branch-width of a connectivity function f is at most k, if f is given by an oracle. This algorithm can be applied to branch-width, carving-width, and rank-width of graphs. In particular, we can recognize matroids Mu of branch-width at most k in polynomial (in vertical bar E(M)vertical bar) time if the matroid is given by an independence oracle. (c) 2006 Elsevier Inc. All rights reserved.