On the computacional complexity of combinatorial flexibility problems

V. A. LEONI, G. L. NASINI

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Taylor & Francis

Lugar: Greenwich; Año: 2010 vol. 87 p. 3330 - 3343

0020-7160

The concept of flexibility---originated in the context of heat exchanger networks design---is associated with a substructure which allows the same optimal value on the substructure (for example an optimal flow) as in the whole structure, for all the costs in a given range of costs.In this work, we extend the concept of flexibility to general combinatorial optimization problems, and prove several computational complexity results in this new framework.Under some monotonicity conditions, we prove that a combinatorial optimization problem can be polynomially reduced to its associated flexibility problem.However, the Minimum Cut, Maximum Weighted Matching and Shortest Path problems have NP-complete associated flexibility problems.In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids.