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 is the co-installability problem, which is related to boolean satisfiability and is known to be algorithmically hard.

This joint work with Jerome Vouillon presents 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 smaller repository can be displayed in a way that provides a concise view of the co-installability issues in the original repository, or used as a basis for studying various problems related to co-installability, and in particular the evolution of co-installability during repository evolution.

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