A method, system and computer program product for minimizing a rule set. A rule set application graph that describes a set of rules including actions and cases is built, whereby each rule defines an action for one or more cases. A rule violation graph for each rule describing the actions and cases not defined for that rule is built. A subset of rules having a reduced number of rules with the same set of actions and cases as the rule set application graph is determined by exploring candidate subsets of the rule set that are sufficient for reproducing the behavior of the original rule set.