Branch-decomposition - Algorithms and Complexity

Algorithms and Complexity

It is NP-complete to determine whether a graph G has a branch-decomposition of width at most k, when G and k are both considered as inputs to the problem. However, the graphs with branchwidth at most k form a minor-closed family of graphs, from which it follows that computing the branchwidth is fixed-parameter tractable: there is an algorithm for computing optimal branch-decompositions whose running time, on graphs of branchwidth k for any fixed constant k, is linear in the size of the input graph.

For planar graphs, the branchwidth can be computed exactly in polynomial time., this in contrast to treewidth for which the complexity on planer graphs is a well known open problem.

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. 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.