Branchwidth, Branch Decompositions and b-parses

Abstract

In this paper we present an easy-to-use data structure for representing graphs of bounded branchwidth, called b-parses. Many hard problems that can be represented as graph problems can be more easily solved when a decomposition of the graph is taken into account. This is particularly true where the input graph can be seen to be treelike in some form. An example of such a treelike structure is branch decomposition, were the edges of a graph are arranged as leaves around a tree and the internal nodes of the tree represent connectivity between subsets of the edges of the original graph. This is similar in concept to the idea of tree decomposition which views the input graph vertices as forming a treelike structure of bounded-sized vertex separators. However branch decompositions may be simpler to work with than tree decompositions for appropriate problems because of the structure (and possibly smaller width) of the tree that is formed. In this paper an algebraic representation of branch decompositions (b-parse) is proposed as an alternative to the t-parse representation for tree decompositions. An application of this data structure to the known hard problems Minimum Vertex Cover and 3-Coloring is examined. Finally, possible benefits of using b-parses from the parallelism perspective is given.