Branch-decomposition

An unrooted binary tree is a connected undirected graph with no cycles in which each non-leaf node has exactly three neighbors.

A branch-decomposition may be represented by an unrooted binary tree T, together with a bijection between the leaves of T and the edges of the given graph G = (V,E).

In particular, in the paper in which they introduced branch-width, Neil Robertson and Paul Seymour[1] showed that for a graph G with tree-width k and branchwidth b > 1, Carving width is a concept defined similarly to branch width, except with edges replaced by vertices and vice versa.

A carving decomposition is an unrooted binary tree with each leaf representing a vertex in the original graph, and the width of a cut is the number (or total weight in a weighted graph) of edges that are incident to a vertex in both subtrees.

[6] As with treewidth, branchwidth can be used as the basis of dynamic programming algorithms for many NP-hard optimization problems, using an amount of time that is exponential in the width of the input graph or matroid.

[7] For instance, Cook & Seymour (2003) apply branchwidth-based dynamic programming to a problem of merging multiple partial solutions to the travelling salesman problem into a single global solution, by forming a sparse graph from the union of the partial solutions, using a spectral clustering heuristic to find a good branch-decomposition of this graph, and applying dynamic programming to the decomposition.

Fomin & Thilikos (2006) argue that branchwidth works better than treewidth in the development of fixed-parameter-tractable algorithms on planar graphs, for multiple reasons: branchwidth may be more tightly bounded by a function of the parameter of interest than the bounds on treewidth, it can be computed exactly in polynomial time rather than merely approximated, and the algorithm for computing it has no large hidden constants.

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.

[17] Forbidden minors have also been studied for matroid branchwidth, despite the lack of a full analogue to the Robertson–Seymour theorem in this case.