Journées de l'optimisation 2007 Optimizations days

The minimum weight feedback vertex set problem (FVS) on series-parallel graphs can be solved in O(n) time by dynamic programming. This solution, however, does not provide a "nice" certificate of optimality. We prove a min-max relation for FVS on series-parallel graphs with no induced subdivision of K2,3 (a class of graphs containing the outerplanar graphs), thereby establishing the existence of nice certificates for these graphs. Our proof relies on the description of a complete set of inequalities defining the feedback vertex set polytope of a series-parallel graph with no induced subdivision of K2,3. We also prove that many of the inequalities described are facets of this polytope.

Recently, graph mining and, in particular, the task of finding the frequent graphs of a database has been the subject of much work. Recent algorithms for this task do well in the general case, but rather poorly when the database graphs have few labels. In this talk, we present a novel algorithm that uses efficient strategies to reduce the search space in cases of high symmetry. Through experimentation on various datasets, we show that our algorithm outperforms current solutions in such cases.

In recent years, computers have played a growing role in the generation and demonstration of theorems in graph theory. One important type of result in graph theory is the characterization of a class of graphs with forbidden subgraphs. In this talk, we present novel methods that automate the characterization of a graph class with forbidden subgraphs, and use these methods to generate some new conjectures.