Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions

Abstract. We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods across a cut of a graph. Boolean-width is similar to rank-width, which is related to the number of GF [2]-sums (1+1=0) of neighborhoods instead of the boolean-sums (1+1=1) used for boolean-width. We give algorithms for a large class of NP-hard vertex subset and vertex partitioning problems that are FPT when parameterized by either boolean-width, rank-width or clique-width, with runtime single exponential in either parameter if given the pertinent optimal decomposition. To compare boolean-width versus rank-width or clique-width, we first show that for any graph, the square root of its boolean-width is never more than its rank-width. Next, we exhibit a class of graphs, the Hsu-grids, for which we can solve NP-hard problems in polynomial time, if we use the right parameter. An n × n 10 Hsu-grid on