Modern software systems are built by composing components drawn from large
  repositories, whose size and complexity is increasing at a very fast pace. A
  fundamental challenge for the maintainability and the scalability of such
  software systems is the ability to quickly identify the components that can or
  cannot be installed together: this problem is related to boolean
  satisfiability and is known to be algorithmically hard.

  We will provide a survey the classic results of this research area, and
  conclude with a short presentation of joint work with Jerome Vouillon: a
  novel approach to the problem, based on semantic preserving graph-theoretic
  transformations, that allows to extract from a concrete component repository
  a much smaller one with a simpler structure, but equivalent
  co-installability properties.

  This approach has been extensively tested on GNU/Linux distributions,
  and can be applied to a large class of component based systems.