6.2.1 The Choice Rule

The Choice Rule

The key insight that we exploit in the algorithm is the following. Suppose you have a node with two incoming dominance edges:

Any solution of this constraint must be a tree (plus binding edges). Since trees don't branch upwards, this means that the only way in which two different nodes can dominate a third one is if one of them, in turn, dominates the other.

Pursuing two alternatives.

Of course we don't know beforehand which of the two has to be the higher node in the solution; in principle, both choices can lead to solutions. We can thus formulate the Choice Rule as follows: If Z is a node with dominance edges from X to Z and Y to Z, add either the dominance edge from X to Y or the dominance edge from Y to X. Graphically:

Because of the argument we just made, we don't lose solutions in this way: Any solution has either the dominance from X to Y or vice versa.

We will refer to this rule both as the Choice Rule (because it chooses either X or Y to dominate the third node) and as the Distribution Rule . This second name is motivated from a programming paradigm called Constraint Programming, in which case distinctions are referred to as "distribution". The Choice Rule is the only case distinction which we use in our enumeration algorithm.