Branch Decomposition¶
A tree arrangement of a graph's edges whose cuts expose shared-vertex interfaces, allowing the arrangement's largest interface to be measured.
Core Idea¶
A branch-decomposition arranges a graph's edges at the leaves of an unrooted cubic tree, one graph edge per leaf. Cutting any edge of the auxiliary tree divides those graph edges into two sets. The middle set contains graph vertices incident to edges on both sides of that split. The largest middle-set size is the width of that decomposition; branchwidth is the smallest such width across all eligible decomposition trees.[^ref-1eb227f6af88]
The decomposition is a formal object, not merely its optimized number. A given tree can establish an upper bound without showing it is optimal. This entry uses ordinary finite graphs with at least three edges; small-graph and generalized connectivity-function conventions should be stated separately. Some graph algorithms exploit a supplied low-width branch-decomposition, but that application is conditional and is not part of the object's identity.[ref-1eb227f6af88][ref-4c9ab63087d1]
Scope of Application¶
This construction belongs literally to structural graph theory and graph algorithms. It exposes nested edge bipartitions and records the shared graph vertices at their boundaries. That is distinct from treewidth's vertex bags and from carving-width's different graph ground set and separator measure. Matroid versions preserve a tree-of-cuts form but use rank-based connectivity and can include a historical plus-one convention; the graph shared-vertex formula does not transfer unchanged.[^ref-1eb227f6af88]
Clarity¶
For a proposed branch-decomposition, ask what labels the tree leaves, which graph-edge split each tree edge displays, and which vertices touch both sides. Then distinguish the observed maximum for this tree from the minimum over all eligible trees. This prevents a convenient drawing from being mistaken for an optimality proof.
Manages Complexity¶
The tree replaces many overlapping graph interactions with a controlled family of cut interfaces. For selected problems, dynamic programming can carry partial information through these interfaces; costs still depend on the particular problem and width. A poor leaf arrangement can expose unnecessarily large interfaces, so the tree must be evaluated by its worst cut rather than merely by the fact that it is tree-shaped.[^ref-4c9ab63087d1]
Abstract Reasoning¶
A proposed tree of width \(k\) proves \(\operatorname{bw}(G)\leq k\). To prove equality, one also needs a lower bound for every eligible tree. In a four-edge star, each nonempty split shares only the center vertex, so every tree has width one. In a four-cycle, pairing adjacent graph edges makes all middle sets size two; every possible tree has singleton-edge cuts of size two, proving branchwidth two. Pairing opposite edges instead yields a central middle set of four vertices and a worse, yet valid, branch-decomposition. These are deductions from the cut definition.[^ref-1eb227f6af88]
Knowledge Transfer¶
Within graphs, the same edge-leaf and middle-set test applies to different finite structures. Outside graphs, only a thinner tree-of-ground-set-cuts idea transfers directly: the ground set and connectivity measure must be specified anew. The broadly portable whole-to-parts relation belongs to live prime Decomposition. Branch-decomposition remains domain-specific because its graph-edge labels and shared-vertex width are constitutive.[^ref-1eb227f6af88]
[^ref-1eb227f6af88]: Susan Jowett, Jasmine Lulani Kaulamatoa and Geoff Whittle, “Bounding branch-width,” Electronic Journal of Combinatorics 30(3) (2023), #P3.21, original article PDF, §2, printed pp. 3–4. [^ref-4c9ab63087d1]: Johan M. M. van Rooij, Hans L. Bodlaender, Erik Jan van Leeuwen, Peter Rossmanith and Martin Vatshelle, “Fast Dynamic Programming on Graph Decompositions” (2018), original arXiv article, author abstract.
Relationships to Other Abstractions¶
Current abstraction Branch Decomposition Domain-specific
Parents (1) — more general patterns this builds on
-
Branch Decomposition is a kind of Decomposition Prime
A branch-decomposition is a graph-specific way to divide an edge ground set into recombinable pieces.
Hierarchy path (1) — routes to 1 parentless root
- Branch Decomposition → Decomposition
Neighborhood in Abstraction Space¶
Branch Decomposition sits in a sparse region of the domain-specific corpus (69th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Two-Terminal Series–Parallel Graph — 0.85
- Hadwiger number — 0.84
- Arboricity — 0.84
- Graph Toughness — 0.83
- Tree (Graph Theory) — 0.83
Computed from structural-signature embeddings · 2026-10-08