Extended skew partition problem

A skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts A1,A2,B1,B2A1,A2,B1,B2 such that there are all possible edges between A1A1 and A2A2, and no edges between B1B1 and B2B2. We introduce the concept of (n1,n2)(n1,n2)-extended skew partition which includes all partitioning problems into n1+n2n1+n2 nonempty parts A1,…,An1,B1,…,Bn2A1,…,An1,B1,…,Bn2 such that there are all possible edges between the AiAi parts, no edges between the BjBj parts, i∈{1,…,n1},j∈{1,…,n2}i∈{1,…,n1},j∈{1,…,n2}, which generalizes the skew partition. We present a polynomial-time algorithm for testing whether a graph admits an (n1,n2)(n1,n2)-extended skew partition. As a tool to complete this task we also develop a generalized 2-SAT algorithm, which by itself may have application to other partition problems.