COMPUTING LARGE SUBCUBES IN RESIDUAL HYPERCUBES

A residual hypercube is an arbitrary subgraph induced by a subset of t he nodes of the hypercube. Residual hypercubes can be used to model th e availability of only some of the nodes of a hypercube, e.g., in faul t tolerance and processor allocation problems. A residual hypercube ma y be specified either by listing all the nodes included in the subgrap h, or else by specifying a collection of subcube descriptors, which ar e n-element strings over {0, 1, } describing all of the available nod es; these variations in representation are useful in designing process or allocation algorithms [1, 3]. We present an efficient algorithm for determining a subcube of maximum dimension in the residual hypercube when all the available nodes are listed explicitly. Given a residual h ypercube of an n-dimensional cube with m available nodes, our algorith m takes time O(nm(2)) time; this compares favorably with the 0(2(m)2(2 m)) algorithm of Ozguner and Aykanat (Inform. Process. Left. 29 (1988) , 247-254) in the case where large numbers of nodes are unavailable. ( The algorithm of Ozguner and Aykanat is superior for small numbers of faults.) We show how to parallelize our algorithm to run on the residu al hypercube in O(n) parallel steps regardless of the size of the resi dual hypercube. We show that when the available nodes are described by subcube descriptors rather than by an explicit list of all available nodes, the problem of finding a maximal-dimension subcube becomes co-N P-hard. Finally, we show that the related problem of finding long cycl es in residual hypercubes is NP-complete. (C) 1995 Academic Press, Inc .