Inverse maximum capacity problems

Let be a finite set, be a family of subsets of and be a capacity vector for all elements of . For each , define the capacity of as the minimum capacity occurring in . The problem which we discuss in this paper is how to change the vector as little as possible so that a given has the maximum capacity. This model contains inverse maximum capacity spanning tree problem, inverse maximum capacity path problem and etc. as its special cases. We transform the problem into the minimum weight cut set problem and show that this problem can be solved efficiently if an efficient algorithm for finding minimum weight cut set of is available. Received: 19 July 1996 / Accepted: 12 November 1997