|
List partition problem for graphs Prof. R. Sritharan University of Dayton, U.S.A. 25-08-03 Abstract Suppose we are given graph G and a symmetric k by k matrix M over {0, 1, *}. We can attempt to partition the vertex-set of G into at most k parts, A1, A2, ..., Ak, subject to the restrictions specified by M interpreted as follows: if M[i,j] = 1 (or 0), then we desire all (or no) edges between vertices placed in Ai and vertices placed in Aj. If M[i,j] = *, then we do not care about adjacencies between vertices in Ai and vertices in Aj. A diagonal entry M[i,i] = 1 (0, or *) specifies that the subgraph induced by Ai be a complete graph (an independent set, or an arbitrary subgraph). The "M-partition problem" asks "Given G and a symmetric k by k matrix M over {0, 1, *}, does G admit a partition subject to M ?". Several well known graph theoretic problems (such as "Is G k-colourable ?", "Does G have a clique-cutset ?") are special cases of the partition problem formulated as above. In an instance of the "list M-partition problem", in addition to being given graph G and a symmetric k by k matrix M as above, for each vertex v of G we are given a list L(v) which is a subset of {A1, A2, ..., Ak}. The problem asks "Is there a partition of G subject to M in which each vertex v is assigned to a part in L(v) ?". List M-partition problem is a generalization of list-coloring as well as list-homomorphism problems. Feder, Hell, Klein, and Motwani (STOC 99) proved that, when k=4, every such list M-partition problem is either solvable in quasi-polynomial time or NP-complete. We prove that for the case k=4, with the exception of one specific problem, every list M-partition problem is either solvable in polynomial time or NP-complete. In proving this, we also show polynomial time solvability of some specific problems whose status was open.
|
