Séminaires 2006 - 2007

10 juillet 2007	Martin C. Golumbic (Haifa)	Twenty years of EPT graphs
07 juin 2007	László Végh (Budapest)	Directed Vertex Connectivity Augmentation
10 mai 2007	Werner Schwaerzler (Bonn)	Flight Schedule Planning and Combinatorial Optimization
26 avril 2007	Francis Lazarus (LIS, Grenoble)	Homotopie et optimisation de courbes sur les surfaces combinatoires
24 avril 2007	Julia Pap (Budapest, Grenoble)	Polyhedral approach to kernels in digraphs
03 avril 2007	Roland Grappe (Grenoble)	Augmentation de l'arête-connexité entre nœuds et zones
07 décembre 2006	Gabor Sarközy (Worcester)	New coloring applications of the Regularity Lemma
07 novembre 2006	Marteen van des Nest (Innsbrück)	Investigating graph problems with quantum information techniques

10 juillet 2007 : Martin C. Golumbic (Université de Haifa, Israël) : Twenty years of EPT graphs.

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, where two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G = EPT(P) for some P and T. The EPT graphs can be useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.

In this invited lecture, we will survey the mathematical and algorithmic results on EPT graphs and some of their generalizations. The class of EPT graphs was first investigated by Golumbic and Jamison in two papers appearing in 1985, and subsequently, further research has been carried out by a number of algorithmic graph theorists. On the algorithmic side, the recognition and coloring problems are NP-complete, whereas the maximum clique and maximum stable set problems are polynomially solvable. On the mathematical side, for example, it was shown 20 years ago, that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. A new analogous result by Golumbic, Lipshteyn and Stern is that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4.

A complete hierarchy of related graph classes will also be presented, including the k-EPT graphs in which paths must share at least k edges of the tree in order to generate an edge in the k-EPT graph. These, together with several restrictions on the tree representation, have been studied recently, and will be presented. We conclude with some open problems and future work.

7 juin 2007 : László Végh (Eötvös Loránd University, Budapest) : Directed Vertex Connectivity Augmentation.

The connectivity augmentation problem is the following: for a given k, add a minimum number of edges to a graph to make it k-connected. As the graph can be both directed or undirected, and one may talk about either edge or vertex connectivity, this general scheme contains four basic problems. Edge connectivity augmentation can be done as a nice application of Mader's splitting-off theorems. For directed vertex connectivity augmentation, I will present the general min-max formula of A. Frank and T. Jordan for covering certain set-pair functions. This formula contains not only the directed vertex and edge connectivity augmentation problems, but also Gyori's theorem on minimum generators of a path system is a consequence. After giving an overview of these problems, I will present the first combinatorial polytime algorithm for directed vertex connectivity augmentation, which we have developed jointly with A. Benczur.

10 mai 2007 : Werner Schwaerzler (Bonn) : Flight Schedule Planning and Combinatorial Optimization.

The production of flight schedules in the airline industry is a process that extends over years and is hardly possible without computerized support, at least for large airlines. It is also a process that holds enormous potential for optimization. This is where combinatorial optimization comes into play. We give an overview of the schedule planning process and provide examples where (sometimes quite simple) optimization methods lead to better results.

26 avril 2007 : Francis Lazarus (LIS, Grenoble) : Homotopie et optimisation de courbes sur les surfaces combinatoires.

Une surface combinatoire est un graphe plongé dans une surface topologique qui dissecte la surface en disques topologiques. Une courbe sur une surface combinatoire est un chemin dans son graphe. Le but de cet exposé est de montrer comment, dans ce cadre combinatoire, on peut répondre à des questions du type : Comment décider si deux courbes sont homotopes ? Quel est le cycle de longueur minimale homotope à un cycle donné ? Peut-on calculer efficacement le plus petit cycle séparateur et non-contractile ? Je reprendrai pour l'essentiel, en développant, un exposé présenté aux journées du GDR Informatique Mathématique :
http://www.lis.inpg.fr/pages_perso/lazarus/

24 avril 2007 : Julia Pap (Budapest, Grenoble) : Polyhedral approach to kernels in digraphs.

In this talk a slight generalization of a theorem of Boros and Gurwich on kernels will be shown. Scarf's lemma which is essential in the proof, will be presented and also an interesting related conjecture. It is a joint work with Tamas Kiraly (University Eotvos, Budapest).

03 avril 2007 : Roland Grappe (Grenoble) : Augmentation de l'arête-connexité entre nœuds et zones.

Etant donnés un graphe G et un entier positif k, combien de nouvelles arêtes faut-il ajouter à G pour que dans le graphe obtenu, entre chaque paire de sommets, il y ait k chaînes arête-disjointes ? Ishii et Hagiwara (2006) ont résolu un problème plus général : étant donné un graphe G=(V,E), une famille W de sous-ensembles de V (les zones) et une fonction de demande r:W->Z⁺, combien de nouvelles arêtes faut-il ajouter à G pour que dans le graphe obtenu, entre chaque sommet v et chaque zone U, il y ait r(U) chaînes arête-disjointes ? Dans cet exposé nous proposons une nouvelle formulation de ce problème et présentons une démonstration significativement raccourcie. (travail commun avec Zoltán Szigeti).
07 décembre 2006 : Gabor Sarközy (Worcester) : New coloring applications of the Regularity Lemma.

We present some new coloring applications of the Regularity Lemma. Among other results, by proving an old conjecture of Faudree and Schelp, we determine the exact three color Ramsey numbers for paths. More precisely we show that R(P_n, P_n, P_n) is 2n-1 if n is odd, and 2n-2 if n is even. This is joint work with Andras Gyarfas, Miklos Ruszinko and Endre Szemeredi.
07 novembre 2006 : Marteen van des Nest (Innsbrück) : Investigating graph problems with quantum information techniques.

In this talk we will consider recent results (joint work with W. Duer and H. Briegel), where we find that certain problems in graph theory can be linked to problems in quantum information theory (QIT), and that mathematical techniques recently developed in QIT can subsequently be used to investigate the initial graph problems.

We will focus on the Tutte polynomial, which is a fundamental graph polynomial related to many graph problems, and which is #P-hard to compute in general. We show that the Tutte polynomial can be reformulated in terms of a so-called 'quantum mechanical amplitude', and that this reformulation allows one to use the machinery of QIT in order to gain insights in the properties of this polynomial. In particular, we show that this approach leads to an efficient algorithm to evaluate the Tutte polynomial for all graphs of bounded tree-width, thereby re-deriving and generalizing a result of [A. Andrzejak, Discr. Math. 190, 39-54 (1998)]. We also discuss generalizations of these results to other problems in discrete mathematics, such as coding theory.

The main idea of the presentation is to explain the general concepts behind the approach, without going into technical physical details, and placing the emphasis on the graph theory and the mathematical concepts. The talk will be a very informal blackboard presentation, intended for an audience of non-physicists.