One embodiment of the present invention provides a system that identifies a substantially minimal set of phase conflicts in a PSM-layout that when corrected renders the layout phase-assignable. During operation, the system constructs a phase-conflict graph from a PSM-layout such that the PSM-layout is phase-assignable if and only if the phase-conflict graph is bipartite. Next, the system removes a first set of edges from the phase-conflict graph to make the graph planar, and then removes a second set of edges to make the graph bipartite. The system then adds zero or more edges of the first set of edges, and determines a set of phase conflicts in the PSM-layout based on the remaining edges in the first set of edges and the second set of edges. The system can also be used to correct a given set of phase conflicts in a PSM-layout.