Feder, Tomas; Hell, Pavol; Klein, Sulamita; Motwani, Rajeev List partitions. (English) Zbl 1029.05143 SIAM J. Discrete Math. 16, No. 3, 449-478 (2003). Summary: List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list “semihomomorphisms.”) Each symmetric matrix \(M\) over \(0,1,*\) defines a list partition problem. Different choices of the matrix \(M\) lead to many well-known graph theoretic problems, often related to graph perfection, including the problem of recognizing split graphs, finding homogeneous sets, clique cutsets, stable cutsets, and so on. The recent proof of the strong perfect graph theorem employs three kinds of decompositions that can be viewed as list partitions. We develop tools which allow us to classify the complexity of many list partition problems and, in particular, yield the complete classification for small matrices \(M\). Along the way, we obtain a variety of specific results, including generalizations of Lovász’s communication bound on the number of clique-versus-stable-set separators, polynomial time algorithms to recognize generalized split graphs, a polynomial algorithm for the list version of the clique cutset problem, and the first subexponential algorithm for the skew cutset problem of Chvátal. We also show that the dichotomy (NP-complete versus polynomial time solvable), conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasi-polynomial) for our list partition problems. Cited in 3 ReviewsCited in 80 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C15 Coloring of graphs and hypergraphs 05C17 Perfect graphs 68Q25 Analysis of algorithms and problem complexity Keywords:list homomorphisms; \(H\)-colorings; graph partitions; perfect graphs; split graphs; skew cutsets; clique cutsets; 2-joins; communication bound; dichotomy; constraint satisfaction problems; quasi-polynomial algorithms; NP-completeness; polynomial time algorithms PDFBibTeX XMLCite \textit{T. Feder} et al., SIAM J. Discrete Math. 16, No. 3, 449--478 (2003; Zbl 1029.05143) Full Text: DOI