Extended skew partition problem

AbstractA skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts A1,A2,B1,B2 such that there are all possible edges between A1 and A2, and no edges between B1 and B2. We introduce the concept of (n1,n2)-extended skew partition which includes all partitioning problems into n1+n2 nonempty parts A1,…,An1,B1,…,Bn2 such that there are all possible edges between the Ai parts, no edges between the Bj parts, 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)-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