Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods - Boolean sums of neighborhoods - across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n(2)k2(2k)) and Minimum Weight Dominating Set in time O(n(2) + nk2(3k)). With an additional n(2) factor in the runtime, we can also count all independent sets and dominating sets of each cardinality. Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Theta(n(2)) vertices has boolean-width Theta(log n) and rank-width, clique-width, tree-width, and branch-width Theta(n). (C) 2011 Elsevier B.V. All rights reserved.