New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem

摘要

Graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tar-jan as a divide-and-conquer approach for solving various problems such as the Maximum Weight Stable Set (MWS) Problem, Coloring and Minimum Fill-in. The basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. We give new examples where the clique separator decomposition works well for the MWS problem which also improves and extends various recently published results. In particular, we describe the atom structure for some new classes of graphs whose atoms are P_5-free (the P_5 is the induced path with 5 vertices) and obtain new polynomial time results for MWS.