2009/03/27 by B. -M. Bui-Xuan, Bui-Xuan, B. -M., J. A. Telle +3
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0903.4796
The new version has runtimes expressed by number of equivalence classes, but no other changes
arxiv created 2011/03/09 · arxiv updated 2011/03/10
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 1/10n2 vertices has boolean-width Θ(log n) and rank-width Θ(n). Moreover, any optimal rank-decomposition of such a graph will have boolean-width Θ(n), i.e. exponential in the optimal boolean-width. A main open problem is to approximate the boolean-width better than what is given by the algorithm for rank-width [Hliněný and Oum, 2008]