This is in contrast to the superficially-similar graph partition problem, in which the cost of a solution is summed over all subsets rather than measured over each, thus bounding the maximum number of partitions. It is sometimes possible to solve a search problem by reducing it to a related decision problem. For example, one might seek to find a satisfying subset assignment for min degree graph partition with the aid of a routine that merely tells whether such an assignment exists. This approach to algorithm design is called self-reducibility , and has been formulated in many ways in the literature. In its most limited form, an assortment of restrictions are placed on the decision algorithm, its input and the lexicographic position of the output produced.
Additional variations exist, some even incorporating randomness or parallelism.
It is not very difficult to see that, for any fixed k and d, min degree graph partition is self-reducible in polynomial time. That is, one can construct a satisfying subset assignment, if any exist, with at most a polynomial number of calls to a decision algorithm, known from the last section also to run in polynomial time. We have been able to show more, namely, that it can in fact be self-reduced with only a linear number of calls. But increasing the size of problem parameters may not be desirable or even possible in many settings. More generally, we seek systematic methods for making such modifications so as to preserve immersion closure.