Sequentially rejective pairwise testing procedures

Holm's (1979) sequentially rejective procedure was developed for families of hypotheses which allow 'free combinations'. Two modifications of Holm's procedure for the family of pairwise hypotheses were discussed by Shaffer (1984, 1986). However, the more powerful modification is only illustrated for the case k = 4 means and not discussed further because of the prohibitive computational effort it requires even when k is moderate. We first note that Shaffer's powerful sequentially rejective procedure is equivalent to Peritz's (1970) closed testing scheme when a natural relation holds between the corresponding critical values. This raises the question of whether conditions exist under which a computationally efficient algorithm can be derived for implementing that procedure. We identified conditions under which a very efficient algorithm is given. While the worst case complexity of Peritz's procedure grows exponentially with k, that of the given algorithm is only a fourth degree polynomial in k. The given conditions are quite restrictive but extremely simple to test in each particular case. This becomes important when k is large since procedures of exponential complexity are not implemented in such cases (and sometimes even when k is moderate). In developing the algorithm we use a graph theory approach and provide some new results which are potentially of independent theoretical interest. © 1987.