On graph classes with logarithmic boolean-width

الأصل · EN

Boolean-width is a recently introduced graph parameter. Many problems are fixed parameter tractable when parametrized by boolean-width, for instance "Minimum Weighted Dominating Set" (MWDS) problem can be solved in O*(2³ᵏ) time given a boolean-decomposition of width k, hence for all graph classes where a boolean-decomposition of width O(n) can be found in polynomial time, MWDS can be solved in polynomial time. We study graph classes having boolean-width O(n) and problems solvable in O*(2ᵒ⁽ᵏ⁾), combining these two results to design polynomial algorithms. We show that for trapezoid graphs, circular permutation graphs, convex graphs, Dilworth-k graphs, circular arc graphs and complements of k-degenerate graphs, boolean-decompositions of width O(n) can be found in polynomial time. We also show that circular k-trapezoid graphs have boolean-width O(n), and find such a decomposition if a circular k-trapezoid intersection model is given. For many of the graph classes we also prove that they contain graphs of boolean-width Θ(n). Further we apply the results from boolw2 to give a new polynomial time algorithm solving all vertex partitioning problems introduced by Proskurowski and Telle TP97. This extends previous results by Kratochvíl, Manuel and Miller KMM95 showing that a large subset of the vertex partitioning problems are polynomial solvable on interval graphs.