Laboratoire d'Informatique de Grenoble

Summary:
In this talk, we consider the problem of modifying the adjacencies of an arbitrary input graph (adding and deleting edges) in order to obtain a graph in a given target class of graphs (i.e. satisfying some properties of interest). Ideally, one would like to be bale to do so using a minimum number of modifications. This problem is usually NP-hard, even for simple target classes. We present some algorithmic approaches to deal with this difficulty of computation, on particular classes of graphs (namely cographs, chordal graphs and ptolemaic graphs), and we highlight some of their possibilities and limitations. We apply some of the algorithms we design on real-world complex networks in order to test how far they are from satisfying some strict mathematical property.