Finding good decompositions for dynamic programming on dense graphs
Jan Arne Telle, Université Bergen

It is well-known that for graphs with high edge density the tree-width is always high while the clique-width can be low. Boolean-width is a new parameter that is never higher than tree-width or clique-width and can in fact be as small as logarithmic in clique-width. Boolean-width is defined using a decomposition tree by evaluating the number of neighborhoods across the resulting cuts of the graph. Several NP-hard problems can be solved efficiently by dynamic programming when given a decomposition of boolean-width k.
In this talk we report on various results related to boolean-width, including a heuristic algorithm that finds a reasonably good decomposition. Experiments with this heuristic show that boolean-width is competitive with tree-width, at least for non-sparse graphs and problems like Independent Set and Dominating Set.