Branch Decompositions and Tree Decompositions
Given a graph G, let T be a tree with |E(G)| leaves and every internal, or non-leaf, node of T having degree three and let n be a bijection from the leaves of T to E(G). (T,n) is a branch decomposition of G. Removing an edge, say e, of T partitions it into what often is referred to as the left and right subtrees. Consequently, G is divided into two subgraphs Ae and Be induced by the edges on the leaves of the left and right trees, respectively. The set V(Ae)ÇV(Be) is called the middle set of e and is denoted by mid(e). A graph can have several different branch decompositions. We say that the width of a branch decomposition is the largest cardinality (or order) of all of its middle sets. Thus, the branchwidth of G, denoted by b(G), is the minimum width over all branch decompositions of G. A branch decomposition of G is said to be optimal if its width is equal to the branchwidth of G.
Cube3 and an optimal branch
decomposition
Given a graph G, let T be a tree. For each vÎV(G), let m(v) denote a subgraph of G. The pair (T, m), is called a tree decomposition if: the union of the m(v)’s is G; for each distinct pair of nodes v and w of T, E(m(v)) and E(m(w)) are disjoint; finally, for all nodes u, v and w of T where v is on the path between u and w, then m(v) Ç m(v) Í m(v). The width of a tree decomposition is the maximum | V(m(v))|-1 for all nodes v of the tree. The treewidth of a graph G, denoted t(G), is the minimum width over all tree decompositions of G. A tree decomposition of G is said to be optimal if its width is equal to the treewidth of G. If the tree of a tree decomposition is restricted to be a path then the pair (T, m) is called a path decomposition and the definition of pathwidth, denoted p(G), is similar to treewidth. Branchwidth and treewidth bound each by the following formula for any simple graph with edges: max(b(G), 2) £ t(G) + 1 £ max( ë(3/2) * b(G)û, 2 ). Any clique of size 3 or above satisfy the upper bound with equality while graphs like cube3 (Kn,n minus a perfect matching for n ³ 4) satisfy the lower bound with equality.
An optimal tree decomposition of
Cube3
Although the concept of tree decompositions (k-trees and partial k-trees) was known before this definition was introduced, tree decompositions were formally introduced by Robertson and Seymour in “Graph Minor I: Excluding a Forest”. Branch decomposition were first introduced by Robertson and Seymour in "Graph Minors X: Obstructions to Tree-Decompositions". These papers are of a series of papers by the authors proving Wagner's Conjecture. Courcelle and others like Arnborg, Lagergren and Seese have proven results characterizing various classes of graph problems which can be solved in polynomial- (even linear-) time when given a branch decomposition of that graph. In contrast, Seymour and Thomas proved that finding optimal branch and tree decompositions of graphs is NP-hard.
Tree decompositions and treewidth have been extensively research. One is referred to the work of Bodlaender for an excellent survey paper. In contrast, research in branch
decomposition have been somewhat ignored.
My research is focused on constructing optimal branch decompositions for
graphs and the construction of branch decomposition based algorithms to solve NP-complete
problems on graphs with bounded branchwidth. I have implemented an heuristic to
compute near-optimal branch decompositions, an improved algorithm based upon an
algorithm of
An optimal branch decomposition
for both Cube3 and the Octahedron