TAOCP 7.1.2 Exercise 74
Let $P$ be the set of unordered pairs ${i,j}$ with $1 \le i < j \le n$ that have not yet been certified as satisfying or failing the decomposition condition tested by the Shen–McKellar–Weiner procedur...
Section 7.1.2: Boolean Evaluation
Exercise 74. [25] Extend the idea in the previous exercise, suggesting a strategy for choosing successive triples $(i, j, m)$ when using the method of Shen, McKellar, and Weiner.
Verified: no
Solve time: 2m10s
Solution
Let $P$ be the set of unordered pairs ${i,j}$ with $1 \le i < j \le n$ that have not yet been certified as satisfying or failing the decomposition condition tested by the Shen–McKellar–Weiner procedure. For a fixed triple $(i,j,m)$ with $i,j,m$ distinct, the test determines whether $m$ serves as a valid separating index for the pair $(i,j)$, in the sense that it witnesses or refutes the required structure involving the variables indexed by $i,j,m$ in the underlying decomposition criterion of the method.
For each fixed $m$, define
$P_m = {{i,j} \in P : i \ne m,\ j \ne m}.$
Each test on a triple $(i,j,m)$ removes the pair ${i,j}$ from $P$ by classifying it according to whether the decomposition condition holds with respect to the mediator index $m$.
The strategy for choosing successive triples is based on maximizing the expected reduction of $|P|$ at each step. For a fixed $m$, the number of pairs in $P_m$ equals the number of pairs that can be tested using $m$ as mediator. Since a single choice of $m$ allows all pairs in $P_m$ to be examined through appropriate choices of $(i,j)$, the effectiveness of selecting $m$ is measured by $|P_m|$.
At each stage, choose an index $m^\ast$ such that
$|P_{m^\ast}| = \max_{1 \le m \le n} |P_m|.$
After fixing $m^\ast$, choose successive pairs $(i,j)$ with $i,j \ne m^\ast$ that remain in $P_{m^\ast}$.
Each test on $(i,j,m^\ast)$ removes ${i,j}$ from $P$, and therefore reduces $|P|$ by one. Recomputing $P_m$ after each elimination updates the distribution of remaining unresolved pairs. The selection rule is then repeated on the updated set.
To refine the strategy further, define for each candidate triple $(i,j,m)$ a score
$\Delta(i,j,m) = |{{u,v} \in P : \text{the test on } (u,v,m) \text{ or } (i,j,m) \text{ resolves } {u,v}}|.$
At each step choose a triple $(i,j,m)$ maximizing $\Delta(i,j,m)$. This ensures that each test contributes maximal immediate elimination of unresolved pairs.
This strategy extends the previous result, where a fixed set of $\binom{n}{2}$ triples suffices, by replacing the static selection with an adaptive greedy choice that continuously concentrates testing on the most informative mediator index $m$ and the most impactful pair $(i,j)$ under the current residual structure of $P$. This produces a successive refinement process in which the remaining candidate space is reduced as rapidly as possible under the SMW testing framework.
This completes the construction of a strategy for choosing successive triples. ∎