This papaer presents two different techniques for relaxing a given test set by maximizing the number of unspecified bits in the test set, without compromising the fault coverage or increasing the test set size. The first method replaces each pattern in the test set with another targeting as few faults as necessary. The second method iterates among faults and enforces detection of a fault only by the test resulting in the largest specified bits reduction. Experimental results show increased reduction rates, even when the input test set has been compacted or already contains unspecified bits, when compared to existing methods. The effectiveness of the proposed methods is demonstrated for two popular test set embedding schemes, using the obtained test sets.