The Complexity of the List Partition Problem for Graphs
Kathie Cameron, Elaine M. Eschen, Chı́nh T. Hoàng, R. Sritharan · SIAM Journal on Discrete Mathematics · 2007
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 eq 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.