Efficient algorithms for graph modification problems (AURORA French-Norwegian project)

Despite the simplicity of their definition, graphs are fundamental objects for computer science. On one side, they are the basis of a number of models in many different application areas (networks, biology, molecular chemistry). On the other side, they capture a large part of the computational complexity. A way to understand the graph structure is to study the combinatorial structure of graph classes (or graph properties). This line of research is motivated by the theoretical insight graph classes could provide, as well as the combinatorial essence of some practical problems. Chordal graphs are a good illustration of this fact: they were introduced for their relationship with the Gaussian elimination process, were the first class to be proved perfect and are meanwhile the natural combinatorial object or model in the perfect phylogeny problem. If the algorithmic / complexity picture of the combinatorial optimization problems is pretty well known on the most important graph classes, much less is known on graphs which almost satisfy a desired property Π (that is a small modification yields a new graph satisfying Π), a common situation of most of the graphs arising from practical data-sets as the measure process may create false positives or false negatives.

Dates: 2012-2013

Project leader: P. Heggernes (University of Bergen, Norway), C. Paul (CNRS, Université Montpellier, France)