AN EFFICIENTLY SOLVABLE GRAPH PARTITION PROBLEM TO WHICH MANY PROBLEMS ARE REDUCIBLE

The 2-Colors Graph Partition problem (2-CGP) is the following: given a graph G(V, E) with colors blue, white, or blue and white assigned to its edges, find a partition A, B of V, if one exists, such that G(A) c ontains no white edges and G(B) contains no blue edges. 2-CGP is a gen eralization of the recognition problem of bipartite graphs and many ot her problems are reducible to it. We prove that 2-CGP is log-space com plete for NLOGSPACE by proving that 2-CGP and 2-CNFSAT are log-space r educible to each other. We describe a parallel algorithm for 2-CGP req uiring O(log n) time and O(n3/(log4n)1.5) processors on a CRCW PRAM wh ich translates into parallel algorithms with the same performance for 2-CNFSAT and 2-QBF Truth.