Boolean-width of graphs |
| |
Authors: | Binh-Minh Bui-Xuan Jan Arne Telle Martin Vatshelle |
| |
Affiliation: | Department of Informatics, University of Bergen, Norway |
| |
Abstract: | 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(n2k22k) and Minimum Weight Dominating Set in time O(n2+nk23k). With an additional n2 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 Θ(n2) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n). |
| |
Keywords: | Graph decomposition FPT algorithm Width parameter Boolean algebra |
本文献已被 ScienceDirect 等数据库收录! |
|