Complexity of graph partition problems
Tomás Feder, Pavol Hell, Sulamita Klein, Rajeev Motwani · 1999
We introduce a parametrized family of graph problems that includes several well-known graph partition problems as special czses.We develop tools which allow us to classify the complexity of many problems in this family, and in particular lead us to a complete classification for small values of the parameters.Along the way, we obtain a variety of specific results including the following: a generalization of a communication bound on the number of clique-versus-independentset separators; polynomial-time algorithms to recognize generalized split graphs; and, a quasi-polynomial algorithm for the Skew Cutset Problem that essentially resolves an open problem posed by Chv&tal.The last two problems have interesting connections to the Strong Perfect Graph Conjecture of Berge.We also observe that the dichotomy (NPcomplete versus polynomial-time solvable) conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasipolynomial) for our graph partition problems.