A computer-implemented method for validating a design characterized by a multi-patterning layer is presented. The method includes receiving the multi-patterning layer in a memory of the computer when the computer is invoked to validate the design. The method further includes correcting, using the computer, a first error in a first shape of the multi-patterning layer in accordance with a first rule thereby forming a corrected layer. The method further includes incrementally validating, using the computer, a first portion of the corrected layer in accordance with the first error and a first connected component of a first graph associated with the multi-patterning layer.