Branch-decomposition - Generalization To Matroids

Generalization To Matroids

It is also possible to define a notion of branch-decomposition for matroids that generalizes branch-decompositions of graphs. A branch-decomposition of a matroid is a hierarchical clustering of the matroid elements, represented as an unrooted binary tree with the elements of the matroid at its leaves. An e-separation may be defined in the same way as for graphs, and results in a partition of the set M of matroid elements into two subsets A and B. If ρ denotes the rank function of the matroid, then the width of an e-separation is defined as ρ(A) + ρ(B) − ρ(M) + 1, and the width of the decomposition and the branchwidth of the matroid are defined analogously. The branchwidth of a graph and the branchwidth of the corresponding graphic matroid may differ: for instance, the three-edge path graph and the three-edge star have different branchwidths, 2 and 1 respectively, but they both induce the same graphic matroid with branchwidth 1. However, for graphs that are not trees, the branchwidth of the graph is equal to the branchwidth of its associated graphic matroid. The branchwidth of a matroid is equal to the branchwidth of its dual matroid, and in particular this implies that the branchwidth of any planar graph that is not a tree is equal to that of its dual.

Branchwidth is an important component of attempts to extend the theory of graph minors to matroid minors: although treewidth can also be generalized to matroids, and plays a bigger role than branchwidth in the theory of graph minors, branchwidth has more convenient properties in the matroid setting. Robertson and Seymour conjectured that the matroids representable over any particular finite field are well-quasi-ordered, analogously to the Robertson–Seymour theorem for graphs, but so far this has been proven only for the matroids of bounded branchwidth. Additionally, if a minor-closed family of matroids representable over a finite field does not include the graphic matroids of all planar graphs, then there is a constant bound on the branchwidth of the matroids in the family, generalizing similar results for minor-closed graph families.

For any fixed constant k, the matroids with branchwidth at most k can be recognized in polynomial time by an algorithm that has access to the matroid via an independence oracle.