Séminaires 2004 - 2005

30 juin 2005	Gautier Stauffer (EPFL)	The stable set polytope of quasi-line graphs
24 mai 2005	Stéphane Vialette (Paris Est)	Finding the largest occurrence of a nested graph that occurs in a set of linear graphs
19 mai 2005	Jeannette Janssen (Halifax)	Limites infinies de modèles de réseaux auto-organisants
11 avril 2005	Stéphan Thomassé (Lyon 1)	Les graphes sans triangle denses sont 4-colorables, une solution au problème d'Erdös-Simonovitz
05 avril 2005	Marton Makai (Budapest)	Even factors and partially dual integral polyhedra
18 novembre 2004	Manouchehr Zaker (Zanjan, Iran)	Rainbow Matchings in Graphs
05 octobre 2004	Irith Hartman (Haifa)	Berge's Conjecture on Directed Path Partitions - A Survey
28 septembre 2004	Egon Balas (Carnegie Mellon)	The vertex separator problem

30 juin 2005 : Gautier Stauffer (EPFL) : The stable set polytope of quasi-line graphs.

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20~years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today.

Such a conjecture exists for the class of quasi-line graphs. This class of graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have 0/1 normal vectors. Ben Rebea's conjecture states that the stable set polytope of a quasi-line graph is completely described by clique-family inequalities. Chudnovsky and Seymour recently provided a decomposition result for claw-free graphs and proved that Ben Rebea's conjecture holds, if the quasi-line graph is not a fuzzy circular interval graph.

In this presentation, we give a sketch of a the proof given by Chudnovsky and Seymour and we also prove that Ben Rebea's conjecture holds true for fuzzy circular interval graphs. This result is the fruit of a joint work with Eisenbrand, Oriolo and Ventura and builds upon an algorithm of Bartholdi, Orlin and Ratliff which is concerned with integer programs defined by circular ones matrices.

24 mai 2005 : Stéphane Vialette (Paris Est) : Finding the largest occurrence of a nested graph that occurs in a set of linear graphs.

In the context of non-coding RNA multiple structural alignment, Davydov and Batzoglou introduced in CPM 2004 the problem of finding the largest occurrence of a nested graph that occurs in a set of linear graphs. In this talk, we give a polynomial-time algorithm for a fixed number of graphs, and strengthen the result of Davydov and Batzoglou by proving that the problem is hard even if the set is composed of nested graphs of height at most 2. Furthermore, both new aproximation and parameterized complexity results are also presented.

19 mai 2005 : Jeannette Janssen (Halifax) : Limites infinies de modèles de réseaux auto-organisants.

Les réseaux auto-organisants sont des réseaux réels ou virtuels qui se forment par des agents indépendants ne possédant que de l'information partielle sur le réseau. Des exemples sont le WWW (sommets = sites Web, arêtes = hyperliens), les graphes formés par des appels téléphoniques, tant que des réseaux biologiques comme le graphe représentant des interactions des protéines dans une cellule. Plusieurs modèles stochastiques ont été proposés pour expliquer la formation de ce type de réseaux. Une partie importante des modèles se base sur le principe de copier: étant donné un sommet v du réseau, une copie de v consiste à ajouter un sommet au réseau en le liant aux voisins de v avec une marge d'erreur.

Une nouvelle méthode pour analyser les modèles de réseaux auto-organisants est de considérer les graphes limites: les graphes infinis obtenus lorsque le temps tend vers l'infinie. Dans cet exposé, je présenterai un modèle général qui se base sur l'idée de copier avec erreur, et des résultats sur ses limites. Je définirai une nouvelle classe de graphes infinis, qui sont la limite unique du modèle dans certain cas. Je montrerai aussi que les limites du modèle possèdent certaines propriété qui sont une version faible de la propriété qui définit R, le graphe aléatoire infini.

Cette recherche a été faite en collaboration avec Anthony Bonato.

11 avril 2005 : Stéphan Thomassé (Lyon 1) : Les graphes sans triangle denses sont 4-colorables, une solution au problème d'Erdös-Simonovitz.

Nous démontrons avec S. Brandt que tout graphe sans triangle dont le degré est > n/3 est 4-colorable. Ce résultat est le meilleur possible puisqu'une construction de Hajnal montre que pour tout e > 0 , le nombre chromatique d'un graphe de degré (1/3 - e)n n'est pas borné.

05 avril 2005 : Marton Makai (Budapest) : Even factors and partially dual integral polyhedra

The role of Integer and dual integral polyhedra in polyhedral combinatorics is that they enable us to derive purely combinatorial statements from polyhedral knowledge. The main goal of this lecture is to present similar techinques when the arising polyhedra are not integer but integer optimal solution exists for a restricted class of weight functions. An example for such a partial dual integral polyhedron is defined by even factors, this polyhedra will be discussed in details (see http://www.cs.elte.hu/egres/tr/egres-03-09.ps.gz). An even factor of a directed graph is the vertex-disjoint union of directed cycles of even lengths and directed paths.

The lecture do not presume deep familiarity with polyhedral combinatorics.

18 novembre 2004 : Manouchehr Zaker (Zanjan, Iran) : Rainbow Matchings in Graphs.

Suppose for each edge e of a graph G we have assigned a subset L(e) of {1,2,...,k} as its color set. A matching {e_1,e_2,...,e_t} is called a rainbow matching if the family {L(e_1),L(e_2),...,L(e_t)} admits a SDR. By the size of rainbow matching we mean the number of edges in its matching. In this talk we discuss on the complexity of determining maximum rainbow matching for union of cycles. This problem is the same as to determine the maximum transversal in a 2-plex. The later object is a well-known kind of sparse partial latin squares. A \lambda-labeling (or radio labeling) of a graph G is any labeling of its vertices with distinct numbers such that any two adjacent vertices receive labels which differ at least two. We show an application of rainbow matchings in the extendibiliy of partial \lambda-labelings and give some results in this regard. We also discuss on other results and unsolved problems concerning rainbow matchings in this talk.

05 octobre 2004 : Irith Hartman (Haifa) : Berge's Conjecture on Directed Path Partitions - A Survey.

Claude Berge is famous for his Perfect Graph Conjecture which was recently proved. In this survey we discuss another, less famous, but no less elegant conjecture related to path partitions in directed graphs. The conjecture is still open, and still intrigues many mathematicians. In the talk, we will survey partial results on the conjecture, some of which are fascinating and deep theorems by themselves. We will look into different proof techniques for these theorems, and relate the conjecture to other conjectures of Berge and others.

28 septembre 2004 : Egon Balas (Carnegie Mellon) : The vertex separator problem.

The vertex separator (VS) problem in a graph G =(V,E) asks for a partition of V into nonempty subsets A, B, C, such that there is no edge between A and B, and |C| is minimized subject to a bound on max{|A|,|B|}. We give a mixed integer programming formulation of the problem and investigate the vertex separator polytope (VSP), the convex hull of incidence vectors of vertex separators. Central to our investigation is the relationship between separators and dominators. Several classes of valid inequalities are investigated, along with the conditions under which they are facet defining for the VSP. Some of our proofs combine in new ways projection with lifting. A branch-and-cut algorithm for the VS problem based on the inequalities discussed here was implemented and tested on a wide variety of VS problem instances drawn from the literature and inspired by various applications. Our computational experience throws new light on the role of cut density as distinct from cut strength.

(Lecture based on joint work with Cid Carvalho de Souza, University of Campinas, Brazil)