The Complexity of the List Partition Problem for Graphs

The $k$-partition problem is as follows: Given a graph $G$ and a positive integer $k$, partition the vertices of $G$ into at most $k$ parts $A_1, A_2, \ldots , A_k$, where it may be specified that $A_i$ induces a stable set, a clique, or an arbitrary subgraph, and pairs $A_i, A_j (i \neq j)$ be completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list $k$-partition problem generalizes the $k$-partition problem by specifying for each vertex $x$, a list $L(x)$ of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list $k$-partition problems: e.g., 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2-clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete.