Equipe Optimisation Combinatoire 
Séminaires 2008 - 2009
- 02 juillet 2009 :
Christophe Picouleau (CNAM - CEDRIC) : d-bloqueurs et d-transversaux des couplages maximums d'un graphe
Given an undirected graph G(V,E) with matching number M(G), a d-blocker is a subset of edges B such that M((V,E\B))=M(G)-d and a d-transversals T is a subset of edges such that every maximum matching M has |M ? T| = d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular bipartitegraphs, grid graph or tree. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs.
- 22 juin 2009 :
Gregory Gutin (University of London) : Algorithms for Discrete Optimization Problems Parameterized Above Tight Lower Bounds
A parameterized problem $\Pi$ can be considered as a set of pairs $(I,k)$ where $I$ is the \emph{main part} and $k$ (usually an integer) is the \emph{parameter}. $\Pi$ is called \emph{fixed-parameter tractable} (FPT) if membership of $(I,k)$ in $\Pi$ can be decided in time $O(f(k)|I|^c)$, where $|I|$ denotes the size of $I$, $f(k)$ is a computable function, and $c$ is a constant independent of $k$ and $I$. If the nonparameterized version of $\Pi$ (where $k$ is just a part of input) is NP-hard, then the function $f(k)$ must be superpolynomial provided P$\neq$NP.
Often $f(k)$ is ``moderately exponential,'' which makes the problem practically feasible for small values of~$k$. Thus, it is important to parameterize a problem in such a way that the instances with small values of $k$ are of real interest.
Consider the following well-known problem: given a digraph $D=(V,A)$, find an acyclic subdigraph of $D$ with the maximum number of arcs. We can parameterize this problem ``naturally'' by asking whether $D$ contains an acyclic subdigraph with at least $k$ arcs. It is easy to prove that this parameterized problem is fixed-parameter tractable by observing that $D$ always has an acyclic subdigraph with at least $|A|/2$ arcs. However, $k\le |A|/2$ for every small value of $k$ and almost every practical value of $|A|$ and, thus, our ``natural'' parameterization is of almost no practical or theoretical interest.
Instead, one should consider the following parameterized problem: decide whether $D=(V,A)$ contains an acyclic subdigraph with at least $|A|/2+k$ arcs. We choose $|A|/2+k$ because $|A|/2$ is a \emph{tight lower bound} on the size of a largest acyclic subdigraph. Indeed, the size of a largest acyclic subdigraph of a symmetric digraph $D=(V,A)$ is precisely $|A|/2$. (A digraph $D=(V,A)$ is {\em symmetric} if $xy\in A$ implies $yx\in A$.)
Mahajan, Raman and Sikdar (J. Comput. Syst. Sci. 75, 2009) asked whether this problem is FPT. Gutin et. al. (arXiv:0906.1356) recently proved that even a weighted version (the linear ordering problem) of this problem is FPT using a probabilistic approach. We will also consider results and deterministic and probabilistic approaches for other optimization problems parameterized above tight lower bounds.
- 11 juin 2009 :
Vladimir Gurvich (RUTCOR) : On graphs whose maximal cliques and stable sets intersect; extending Cameron-Edmonds-Lovasz' theorem (Joint work Diogo Andrade and Endre Boros)
We say that a graph $G$ has the CIS-property and call it a CIS-graph if every maximal clique and every maximal stable set of $G$ intersect.
By definition, $G$ is a CIS-graph if and only if the complementary graph to $G$ is a CIS-graph.
Let us substitute a vertex $v$ of a graph $G'$ by a graph $G''$ and denote the obtained graph by $G$. It is also easy to show that $G$ is a CIS-graph if and only if both $G'$ and $G''$ are CIS-graphs.
Thus, CIS-property is closed under the complementation and substitution. Yet, it is not hereditary, that is, an induced subgraph of a CIS-graph might have no CIS-property. Perhaps, for this reason, the problemsof efficient characterization and recognition of CIS-graphs are difficult and remain open. We only give some necessary and some sufficient conditions for the CIS-property to hold.
There are obvious sufficient conditions. It is known that $P_4$-free graphs have the CIS-property and it is easy to see that $G$ is a CIS-graph whenever each maximal clique of $G$ has a simplicial vertex. [The last observation implies that any graph can be an induced sibgraph of a CIS-graph.] However, the above two conditions are not necessary.
There are also obvious necessary conditions. Given an integer $k \geq 2$, a {\em comb} $S_k$ is a graph with $2k$ vertices $k$ of which, $v_1, \ldots, v_k,$ form a clique $C$, while others, $v'_1, \ldots, v'_k,$ form a stable set $S$, and $(v_i,v'_i)$ is an edge for all $i = 1, \ldots, k,$ and there are no other edges. The complementary graph $\overline{S_k}$ is called an {\em anti-comb}. Clearly, $S$ and $C$ switch in the complementary graphs. Obviously, the combs and anti-combs are not CIS-graphs, since $C \cap S = \emptyset$. Moreover, every induced comb or anti-comb must be settled, that is, $G$ must contain a vertex $v$ connected to all vertices of $C$ and to no vertex of $S$. However, these conditions are only necessary.
The following sufficient conditions are much more difficult to prove: $G$ is a CIS-graph whenever $G$ contains no induced $3$-combs and $3$-anti-combs, and every induced $2$-comb is settled in $G$.
This result was conjectured in early 90s by Chvatal and proved in 2004 by Deng, Li, and Zang. In 2006, we got an alternative proof in which the sum of two Petersen's graphs plays an important role.
It is an open question whether $G$ is a CIS-graph if $G$ contains no induced $4$-combs and $4$-anti-combs, and all induced $3$-combs, $3$-anti-combs, and $2$-combs are settled in $G$.
A graph $G$ is called {\em almost CIS} if there is a unique disjoint pair $(C_0, S_0)$, while all other maximal cliques and stable sets of $G$ intersect. It is easy to verify that the split qraphs (with a unique split partition $C_0 \cup S_0$ ) satisfy this property. One can naturally conjecture that there are no others. Somewhat surprisingly, this conjecture appears to be pretty difficult. It was proved in 2009 by Wu, Zang, and Zhang.
We generalize the concept of CIS-graphs as follows. For an integer $d \geq 2$ we define a $d$-{\em graph} $\cG = (V; E_1, \ldots, E_d)$ as a complete graph whose edges are colored by $d$ colors, or partitioned in $d$ sets. We say that $\cG$ is a CIS-$d$-graph (has the CIS-$d$-property) if $\cap_{i=1}^d S_i \neq \emptyset$ whenever $S_i$ is a maximal stable set of the graph $G_i = (V, E_i)$ for $i = 1, \ldots, d$. Clearly, in case $d=2$ we return to the concept of CIS-graphs. [More accurately, CIS-2-graph is a pair of two complementary CIS-graphs.] We conjecture that each CIS-$d$-graph is a Gallai graph, that is, it contains no triangle $\Delta$ colored by 3 distinct colors. We obtain results supporting this conjecture and also show that if it holds then the characterization and recognition of CIS-$d$-graphs can be easily reduced to the case $d=2$, that is, to to the characterization and recognition of CIS-graphs.
We also prove the following statement. Let $\cG = (V; E_1, \ldots, E_d)$ be a Gallai $d$-graph such that at least $d-1$ of its $d$ chromatic components are CIS-graphs, then $\cG$ has the CIS-$d$-property. In particular, the remaining chromatic component of $\cG$ is a CIS-graph too. Moreover, all $2^d$ unions of $d$ chromatic components of $\cG$ are CIS-graphs.
In fact, this statement holds not only for the CIS-property but for any property $P$ of graphs closed with respect to the complementation and exactly closed with respect to substitution. Cameron and Edmonds proved this in 1997, assuming additionally that $P$ is hereditary. Earlier, in 1986, Cameron, Edmonds, and Lovasz proved this for the case $P$ = perfectness.
Let us finally note that, CIS-$d$-property holds for the $\Pi$- and $\Delta$-free $d$-graphs, where $Pi$ is the $2$-graph whose each component is $P_4$, while $\Delta$ is the $3$-colored triangle. It is known that these $d$-graphs are in one-to-one correspondence with positional game forms with perfect information.
- 07 mai 2009 :
Frédéric Meunier (ENPC) : Carathéodory, Helly et les autres dans le monde tropical
Dans un autre monde, additionner deux nombres consiste à prendre leur maximum et les multiplier consiste à les additionner. On appelle ce monde, le monde tropical. Dans le monde tropical, il y a aussi une géométrie, et de la convexité. Et on sait depuis longtemps que les théorèmes de Carathéodory, Helly et Radon y existent.
Ces théorèmes ont de très belles généralisations pour la convexité usuelle: il s'agit par exemple des théorèmes de Carathéodory coloré ou de Tverberg. Il est naturel de se demander si ces derniers ont également des versions tropicales. Nous verrons que la réponse est oui. De plus, une célèbre conjecture (la dutch cheese conjecture) en rapport avec le théorème de Tverberg, toujours ouverte pour la convexité usuelle, s'avère être vraie pour la convexité tropicale.
Les preuves sont de nature purement combinatoire et s'appuient entre autres sur des propriétés variées des couplages dans les graphes bipartis. (Travail en collaboration avec Stéphane Gaubert).
- 05 mai 2009 :
Imre Barany (Budapest & Londres) : Paths with no small angle
Given a finite set X in the plane, does there exist a polygonal path P, whose vertex set is exactly X, such that all angles of P are at least one degree?
This question, its solution, and some related problems will be discussed in this talk. The results are joint work with Attila Por and Pavel Valtr.
- 27 avril 2009 :
Jack Edmonds (Université Pierre et Marie Curie) : Finding Another
An 'Existentially Polytime (EP) theorem' is one which, like 'good characterization', asserts the existence of something any instance of which is easy to recognize relative to the size of the hypothesis-instance. Most of the structural existence theorems regarded by combinatorists as pretty are EP.
We continue to advocate studying algorithms which find an instance of what an EP theorem says exists -
For example, a direct algorithm for the theorem that:
In any graph, there exists either a Berge obstruction or a clique and coloring the same size.
Or for the theorem that:
For any closed-surface triangulation, and for any subset of its triangles which partitions its vertices, there exists another different subset of its triangles which partitions its vertices.
Or for the theorem that:
For any Hamiltonian path P in a graph G such that G minus the edges of P is connected, there exists another different Hamiltonian path in G with the same ends as P.
Article téléchargeable : "Euler Complexes"
- 27 avril 2009 :
Kathie Cameron (Equipe Combinatoire et Optimisation, Université Paris VI) : Finding An Intermediate Spanning Tree
The intermediate spanning tree problem is: Given two distinct spanning trees, T and T', of a graph G, is there another spanning tree, T", of G such that the degree of each vertex of T" is between its degree in T and its degree in T'.
A theorem of Ken Berman implies that if T and T' are edge-disjoint and do not have the same degree at each vertex, then an intermediate tree exists. An old algorithm given by Jack Edmonds and me finds an intermediate tree in this case.
Joanna Fawcett and I have characterized the graphs in which no pair of spanning trees have an intermediate tree. We have found some classes of graphs in which every pair of spanning trees has an intermediate tree. In most cases, an intermediate tree can be found by adding at most one edge to G. - 23 avril 2009 :
Christophe Crespelle (Jussieu) : Représentations de graphes pour l'algorithmique et la modélisation
L'exposé abordera trois problématiques de représentation des graphes.
La première concerne les graphes d'intervalles et le maintien dynamique d'un modèle d'intersection lorsque le graphe subit des modifications d'arête ou de sommets. La solution proposée repose sur l'utilisation des PQ-arbres et de la décomposition modulaire, dont nous montrons l'équivalence pour les graphes d'intervalles, et débouche sur un algorithme traitant les quatre opérations élémentaires (ajout et retrait d'arête ou de sommet) en temps O(n).
La seconde partie de l'exposé sera consacrée à un problème de modélisation des graphes de terrain, qui sont des graphes de taille très importante rencontrés dans divers contextes pratiques. Récemment, il a été proposé de modéliser ces graphes par le biparti d'incidence des cliques maximales et des sommets. Cela a permis de générer aléatoirement des graphes dont on contrôle à la fois la distribution des degrés et le coefficient d'agglomération, ce qui n'avait jamais été réalisé jusqu'à lors. L'approche souffre néanmoins d'un inconvénient majeur que nous essaierons de corriger par l'introduction d'un modèle multiparti basé sur la factorisation récursive des intersections de voisinages dans le biparti. Nous aborderons la question de la convergence de ce procédé et montrerons des liens forts avec une structure combinatoire bien connue, l'ordre d'inclusion des intersections de cliques maximales.
Enfin, nous nous intéresserons à la possibilité de représenter les voisinages dans un graphe de permutation de manière compacte. Le modèle d'intersection de ces graphes requiert un espace O(n) et répond aux requêtes d'adjacence entre deux sommets en temps constant. Qu'en est-il des requêtes de voisinages? Nous construirons une structure de taille O(n) qui permet de lister le voisinage d'un sommet de degré d en temps O(d). Nous donnerons un algorithme de parcours en largeur d'un graphe de permutation qui fonctionne en temps O(n), améliorant ainsi la complexité du problème des plus courts chemins, à origine unique et entre toutes les paires, sur cette classe de graphes.
- 23 avril 2009 :
Roland Grappe (G-SCOP) : Augmentation de l'arête-connexité d'un hypergraphe en lui ajoutant un graphe multiparti
Un (hyper)graphe est k-arête-connexe si entre toutes paires de sommets il existe k chemins (hyper)arête-disjoints. L'augmentation de l'arête-connexité d'un graphe consiste à, étant donnés un graphe G et un entier k, ajouter un nombre minimal d'arêtes à G pour le rendre k-arête-connexe. Grâce à l'algorithme de Frank, qui résout ce problème, de nombreuses extensions ont vu le jour : par exemple pour les hypergraphes, ou encore avec des contraintes supplémentaires sur les arêtes à ajouter. Nous proposons de résoudre la généralisation suivante.
Problème : Soit H=(V,E) un hypergraphe, P une partition de V, et k un entier. Ajouter un nombre minimal d'arêtes de taille 2 reliant différents membres de P à H pour le rendre k-arête-connexe. Nous exhibons deux bornes inférieures naturelles pour ce problème, et caractérisons les hypergraphes pour lesquels ces bornes ne peuvent pas être atteintes. Un théorème min-max résolvant le problème en découle, accompagné d'une preuve constructive et polynomiale. - 02 avril 2009 :
Jean Fonlupt (Jussieu) : Extrémités du segment d'intersection entre un polytope et une droite
Soit P un polytope plongé dans un espace affine de dimension n. Nous cherchons à calculer les extrémités du segment intersection de P et d'une droite Delta. Quand P est décrit a partir de ses points extrêmes, ce problème est ouvert et difficile car il fournirait un algorithme combinatoire polynomial de type simplexe pour la programmation linéaire. Si P est décrit par un système d'inégalités linéaires le problème est trivial si la description des contraintes fait partie de l'input. Le cas intéressant est quand P est décrit par un nombre exponentiel de contraintes et que le problème d'optimisation est polynomial sur P (couplage, matroïdes). Nous nous intéresserons au cas des polymatroïdes car notre problème résout alors le problème de la minimisation d'une fonction sous-modulaire et de la force d'un graphe. Nous présenterons un algorithme polynomial déterministe mais aussi en probabilité quand les coefficients directeurs de la droite sont tirés.
- 30 mars 2009 :
Tom McCormick (Université de Colombie-Britannique) : Monotone parametric min cut revisited: structures and algorithms
We consider the min cut problem when capacities depend on a parameter $\lam$. There are some classes of this parametric min cut problem that are known to have the nice structural property that min cuts are nested in $\lam$, and the nice algorithmic property that all min cuts can be computed in the same asymptotic time as a single min cut computation. We extend these results in several directions: we find three much more general classes of problems for which these two nice properties continue to hold, and we extend other results with the same flavor as well.
- 19 mars 2009 :
Guyslain Naves (G-SCOP) : Tournée et partition d'éclatement maximum
Un ensemble éclatant dans un graphe est un ensemble S de sommets qui, lorsqu'on les retire, coupe le graphe en plus de composantes connexes que |S|, i.e. c(S) > |S|. Nous cherchons à trouver des classes de graphes pour lesquels la longueur d'une plus courte marche fermée passant par tous les sommets est donnée par la valeur maximum d'un packing d'ensembles éclatants. Nous montrerons en particulier que les graphes d'intervalles vérifient cette propriété.
- 05 mars 2009 :
Gregor Masbaum (Jussieu) : The Pfaffian-Tree Theorem
The well-known matrix-tree theorem of Kirchhoff expresses the number of spanning trees of a graph via the determinant of some matrix related to its adjacency matrix. In this talk, I will discuss a new matrix-tree theorem discovered by A. Vaintrob and myself, which expresses the spanning-tree polynomial of a 3-uniform hypergraph as a Pfaffian. This result was motivated by considerations from knot theory, but it can be understood in completely elementary terms. If time allows, I will also discuss a curious application of our formula to complexity theory.
- 02 février 2009 :
Simone Dantas (Niteroi) et Ana Silva (Grenoble) : Four nonempty
part partition problems and recent advances in the 2K_2-partition problem
Every partition problem into 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem, the 2K_2-partition problem, for which the complexity of the corresponding list problem is known to be NP-complete. In this talk, we recall the history of the problem and we show recent advances in this area.
- 22 janvier 2009 :
Louis Esperet (Prague) : Compter les couplages parfaits dans les
graphes cubiques
Lovasz et Plummer ont conjecturé dans les années 70 que les graphes cubiques 2-arête-connexes ont un nombre exponentiel de couplages parfaits. Cela a été montré pour les graphes bipartis en 1979 par Voorhoeve, et très récemment pour les graphes planaires par Chudnovsky et Seymour. Dans le cas général les meilleures bornes connues sont linéaires : Edmonds, Lovász, et Pulleyblank, et indépendamment Naddef, ont prouvé en 1982 que la dimension du polytope des couplages parfaits d'un graphe cubique 2-arête-connexe à n sommets est au moins n/4+1 (ce qui implique directement qu'ils ont au moins n/4+2 couplages parfaits). En utilisant un résultat récent de Král', Sereni, et Stiebitz, nous montrons que tout graphe cubique 2-arête-connexe à n sommets a au moins 3n/4-10 couplages parfaits. Notre preuve est inductive et repose largement sur la "brick and brace decomposition" introduite par Edmonds, Lovász, et Pulleyblank en 1982.
- 08 janvier 2009 :
Flavia Bonomo (Buenos Aires) : On
graph coloring problems with local constraints
The graph coloring problem is a basic model for frequency assignment and resource allocation problems. In order to take into account particular constraints arising in practical settings, more elaborate models of vertex coloring have been defined in the literature. One of such generalized models is the list-coloring problem, which considers a prespecified set of available colors for each vertex. Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. Meanwhile, the list-coloring problem is NP-complete for general perfect graphs, and is also NP-complete for many subclasses of perfect graphs, including split graphs, interval graphs, and bipartite graphs. In this talk, we will analyze some coloring problems lying "between" (from a computational complexity viewpoint) these two problems, and having themselves applications as models for practical problems.
- 18 décembre 2008 : Claudia Linhares
Sales (Université Fédérale du Cearà) : The Proportional Colouring Problem
We consider a new edge colouring problem: the proportional edge-colouring. Given a graph G with positive weights associated to its edges, we want to find a colouring which preserves the proportion given by the weights associated to each edge. If such colouring exists, we want to find one using a minimum number of colours. We proved that deciding if a weighted graph admits a proportional colouring is polynomial while determining its proportional chromatic index is NP-hard. In addition, we give a lower bound and an upper bound for this parameter that can be computed in polynomial time. We finally show a class of graphs and a class of weighted graphs for which we can exactly determine the proportional chromatic index.
- 11 décembre 2008 :
Anna Silva (Grenoble) : Treewidth of even-hole-free planar graphs
The class of planar graphs has unbounded treewidth, since the k × k grid, for all integer k, is planar and has treewidth k. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. We show that if G is an evenhole-free planar graph, then it does not contain a 9 × 9 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 44.
- 11 décembre 2008 :
Attila Bernath (Budapest) : A simple proof of a theorem of Benczúr
and Frank
The main problem is to cover a symmetric, crossing supermodular set function with a minimum number of graph edges. Special cases include augmenting a graph to become $k$-edge-connected (theorem of Watanabe and Nakamura) or augmenting a hypergraph with graph edges to become $k$-edge-connected (this was solved by Bang-Jensen and Jackson). The general problem was solved by Bencz\'ur and Frank, the proof relies on the splitting-off technique. I want to show a simple proof of this theorem using a little bit different approach to splitting-off.
- 27 novembre 2008 :
Gabor Sarkozy
(Worcester) : On the Regularity Method
The Regularity method based on the Regularity Lemma and the Blow-up Lemma has been a very successful method in the theory of dense graphs and hypergraphs. In this talk we overview the history and the basics of the method. We show some results that we were able to obtain with this method. In particular we will focus on one problem where the method has been productive, namely finding various kinds of cycles in hypergraphs.
Co-authors on this work included Paul Dorbec, Sylvain Gravier, Andras Gyarfas, Jeno Lehel, Richard Schelp and Endre Szemeredi.
- 11 septembre 2008 : András
Gyárfás (Budapest) : Ramsey type results in
G(allai)-colorings
A G-coloring of a complete graph is an edge coloring that does not contain triangles colored with three different colors. Since G-colorings generalize 2-colorings, it is natural to study how Ramsey type results for 2-colorings carry over to G-colorings. A basic tool for that is the following theorem, discovered by many authors in different forms and contexts, perhaps first (implicitly) in Gallai’s work on comparability graphs. The form below is from Gyárfás and Simonyi.
Any G-coloring can be obtained by substituting G-colored complete graphs into vertices of a nontrivial 2-colored complete graph.
Based on this structure theorem, certain results - every 2-colored complete graph has a monochromatic spanning tree; has a monochromatic spanning diameter three subgraph - carry over almost automatically to G-colorings. In case of some other results more work is needed, usually to work out a a weighted version of the statement to be carried over to G-colorings. It may also happen that a result for 2-colorings has no counterpart for G-colorings. For example, for n ≥ 6, Kn has a monochromatic triangle in every 2-coloring but no Kn has this property for every G-coloring.
The phenomenon showed in the last example disappears if the number of colors is fixed in G-colorings. Let R(k) be the smallest integer m such that there is a monochromatic triangle in every k-coloring of Km. Let GR(k) be defined similarly, restricting ourselves to G-colorings with k colors. It is a very difficult open problem to narrow the known bounds of R(k) (ck ≤ R(k) ≤ [ek!] + 1). What about GR(k)?