On the computational complexity of combinatorial flexibility problems

Abstract

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.

Keywords:

• combinatorial problems
• test sets
• flexibility problems
• computational complexity
• matroids

2000 AMS Subject Classifications :

• 90C27
• 90C35
• 90C60
• 68Q25

Acknowledgements

We are indebted to N. Aguilera for kindly sharing with us his findings in this subject and encouraging us to finish this work. We also want to deeply thank the anonymous referees who helped us in improving this presentation.