2010-2011
2010 - 2011
Vendredi 10 Septembre 2010 - Improved approximability and non-approximability results for graph diameter decreasing problems - Davide Bilo (Université de L'Aquila, Italie).
Résumé : We study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph G = (V, E), and two positive integers D and B, the Minimum-Cardinality Bounded-Diameter Edge Addition (MCBD) problem is to find a minimum cardinality set F of edges to be added to G in such a way that the diameter of G+F is less than or equal to D, while the Bounded-Cardinality Minimum-Diameter Edge Addition (BCMD) problem is to find a set F of B edges to be added to G in such a way that the diameter of G + F is minimized. Both problems are well known to be NP-hard, as well as approximable within O(log n log D) and 4 (up to an additive term of 2), respectively. In this paper, we improve these long-standing approximation ratios to O(log n) and to 2 (up to an additive term of 2), respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of the MCBD problem, which was known to be not approximable within c log n, for some constant c > 0, unless P = NP. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution 5 whose diameter is optimal up to a multiplicative factor approaching 3. On the other hand, on the positive side, we show that at most twice of the minimal number of additional edges suffices to get at most twice of the required diameter.
Vendredi 17 Septembre 2010 - Problèmes ouverts de coloration et NP-completude - Pascal Ochem (LRI, Orsay)
Résumé : Une conjecture bien connue dit notamment que les graphes
planaires de maille 8 ont un homomorphisme vers le cycle de taille 5.
On montre que si la conjecture est fausse, alors decider si un graphe
planaire de maille 8 admet un homomorphisme
vers le cycle de taille 5 est un problèmes NP-complet.
On donnera aussi des résultats du même genre pour d'autres
problèmes ouverts de coloration.
Vendredi 1 Octobre 2010 - Surveillance de réseaux éléctriques, Power Domination - Paul Dorbec
Résumé : Power domination was introduced by Haynes et al as a graph theoretical description of a physical problem. The initial problem, proposed by Baldwin et al was to monitor an electrical network by placing as few
phase measurement units as possible.
A phase measurement unit placed on a vertex of a graph permits to monitor all the vertices of its closed neighborhood. Then, thanks to Kirschoff laws, any monitored vertex adjacent to only one unmonitored vertex allows to also monitor this neighbour. With these rules, a power dominating set is a set of vertices that allows to monitor the whole graph. The power domination number is the minimum cardinality of a power dominating set.
This definition of the problem induces some propagation phenomenon that is uncommon in domination problems, and looks more like the behaviour of some life game. For exemple, the power domination of a path is only one, however long the path is.
During this talk, we shall present a common generalization of domination and power domination, denoted k-power domination. In this variant, a monitored vertex adjacent to at most k unmonitored neighbours allows to have these neighbours monitored. When k=1, this is the power domination, and usual domination corresponds to the case when k=0. Surprisingly, studying this new variant, we managed to extend some classical domination results to k-power domination, like for exemple a linear algorithm for trees very different from the algorithm proposed by Haynes et al. We also extended various results of power domination to k-power domination.
Vendredi 15 Octobre 2010 - Vertex distinguishing labelings of graphs - Jakub Przybylo
Résumé : Let G be a simple connected graph of order n ≥ 3, and let us label each edge of G with a positive integer. As a result we obtain a vertex colouring, where the colour of a vertex is defined by the sum of the numbers on its incident edges. Suppose we use only integers 1,2,...,k as labels. How large must k be for a given graph G ? A striking conjecture of Karonski,Luczak and Thomason asserts that the numbers 1, 2, 3 are sufficient for every graph. We shall discuss best known results in pursuit of the proof of this conjecture, as well as a number of related problems. Among others, we will focus on the “total” counterpart of this conjecture (where also vertices obtain their own initial labels), and the problem where all the vertices, not only the neighbouring ones, are required to have distinct colours (i.e., sums). The later introduces a well known graph invariant called irregularity strength of a graph.
Vendredi 22 Octobre 2010 - Une étude du jeu de COL - Gabriel Renault.
Résumé : COL est un jeu combinatoire partisan de coloration de graphes inventé par Colin Vout. En attribuant des valeurs aux instances, on déterminera des stratégies gagnantes sur certaines classes de graphes : les cographes et certaines sous-classes d'arbres.
Vendredi 26 Novembre 2010 - Sur la dimension cubique de quelques classes d'arbres - Kamal Kabyl (Université A/Mira de Béjaia).
Résumé : Arffati, Papadimitriou et Papageorgiou ont montré que le problème de décider si un graphe G est plongeable dans un hypercube de dimension donnée est NP-complet. Corneil et Wagner ont montré que ce problème reste NP-complet même dans le cas où G est un arbre. Plusieurs auteurs se sont intéressés à l’étude de plongement d’arbres dans l’hypercube ce qui a permis de caractériser certaines classes.
Tous les arbres sont plongeables dans l’hypercube, le problème consiste à donner la plus petite dimension d’un hypercube dans lequel un arbre donné est plongeable. On parle alors d’hypercube optimal et de la dimension cubique de l’arbre. De nombreux problèmes (booléens, de théorie des graphes, de codes…) sont formalisables comme problèmes combinatoires sur l’hypercube, donc il est fondamental de déterminer quels sont les graphes et particulièrement les arbres qui sont plongeables dans l’hypercube et de déterminer aussi combien de copies d’un arbre donné on peut placer (de façon disjointe) dans un hypercube de dimension donnée.
Nous avons introduit quelques classes d’arbres pour lesquelles nous avons déterminé la dimension cubique et nous avons aussi donné pour certaines classes le nombre maximum de copies que l’on peut placer dans un hypercube de dimension donnée.
Un problème d’une autre nature a été traité, il concerne la détermination du nombre de sommets minimum et du nombre de sommets maximum d’une famille de graphes plongeables dans un même hypercube optimal.
Mots-clés : Hypercube, Plongement, Graphe, Arbre, Isomorphisme.
Vendredi 3 Décembre 2010 - Largeur arborescente et dualité sur les surfaces - Frédéric Mazoit.
Résumé : Dans Graph Minor 3, Robertson et Seymour on écrit:"It seems that the tree-width of a planar graph and the tree-width of its geometric dual are approximately equal — indeed, we have convinced ourselves that they differ by at most one." Dans cet exposé, je présenterai une preuve d'une généralisation de cet "exercice" laissé au lecteur en genre supérieur et je montrerai que ce résultat est optimal.
Vendredi 10 Décembre 2010 - Codes identifiants, systèmes de contrôle et graphes sans-jumeaux. - David Auger.
Résumé :
Un code identifiant dans un graphe est un ensemble dominant C tel que tous les sommets du graphe soient dominés par un ensemble d'éléments de C qui leur soit propre. Nous présenterons cette notion, ainsi que les variantes à distance r fixée et les codes identifiant les ensembles de sommets. On fera un panorama des recherches concernant ces codes : bornes, algorithmes, complexité, ainsi que des graphes sans-jumeaux, intrinsèquement liés aux codes identifiants. Enfin, nous introduirons la notion de système de contrôle, variante des codes identifiants possédant quelques propriétés intéressantes.
Vendredi 14 janvier 2011- On Lovasz's number of powers of chordless cycles - Arnaud Pêcher.
Résumé : The Lovasz number (or Theta function) theta(G) of a graph G is a famous real graph parameter computable in polynomial time, which is sandwiched between the clique number and the chromatic number of its complement. The circular-chromatic number is a well studied rational refinement of the chromatic number.
In this work, we present some closed formulas of the Lovasz number of powers of chordless cycles and use them to prove the polynomial time computability of the circular-chromatic number of some superclasses of perfect graphs.
This is a joint work with C. Bachoc and A. Thiery.
Vendredi 21 Janvier 2011 - Rainbow matchings: existence and counting - Guillem Perarnau (UPC, Barcelona).
Abstract : Given an edge coloring of a graph, a rainbow matching is a matching where all the edges have different color. In particular we focus on the case when the graph is the complete bipartite graph K(n,n). This problem is analogous to find a latin transversal in integer matrices. A result from Erdos and Spencer (1988) states that if no color appears more than n/4e times then the coloring admits a rainbow matching. In this talk we will show some existence and enumeration results subject to these type of constraints. The Lovasz Local Lemma will be used as a main tool in the sense of Poisson Paradigm. Random models of colorings will be introduced and discussed.
This is a joint work with O.Serra.
Vendredi 4 février 2011 - fusion avec le séminaire de théorie des nombres : Graphes de très grande maille fondés sur les octonions - Jean-Pierre Tillich.
Résumé : La maille d'un graphe est définie comme la plus petite taille d'un cycle dans ce dernier. Une vieille question en théorie des graphes consiste à étudier quelle est la plus grande maille possible pour un graphe $d$-régulier (c'est à dire un graphe où chaque sommet comporte $d$ arêtes) et à proposer des familles de graphe atteignant la borne. La meilleure borne supérieure sur la maille est de l'ordre de $(2+o(1)) \log_{d-1} n$ quand le nombre de sommets $n$ tend vers l'infini. De nombreuses constructions atteignant une maille de taille logarithmique en le nombre de sommets ont été proposées par le passé. La construction la plus célèbre est sans nul doute une construction arithmétique fondée sur les propriétés de factorisation des quaternions due à Margulis, Lubotzky, Philips et Sarnak datant de la deuxième partie des années 1980. De manière remarquable, cette construction a aussi fourni la première famille infinie de graphes $d$-réguliers qui soit de Ramanujan (c'est une propriété remarquable portant sur le spectre du graphe). La maille de cette famille est de l'ordre de $4/3 \log_{d-1}n$ et c'était jusqu'à présent la meilleure construction connue pour la propriété de maille. Nous nous inspirons de cette construction fondée sur les quaternions pour proposer une nouvelle construction à base d'octonions dont la maille est de l'ordre de $12/7 \log_{d-1} n$ nous rapprochant ainsi un peu plus de la borne supérieure susmentionnée. Nous montrons aussi, comme dans le cas de la construction à base de quaternions, que cette nouvelle famille est aussi de Ramanujan par un argument de comptage du nombre de solutions d'une certaine équation diophantienne quadratique.
travail effectué en commun avec Xavier Dahan
Vendredi 11 février 2011 - Vertex partitions of graphs - Mickael Montassier.
Résumé : Dans cet exposé, nous parlerons de partition des sommets d'un graphe où le graphe induit par chaque ensemble de la partition est une forêt d'étoiles ou un cographe et répondrons à une question de Gimbel et Nesetril sur le sujet. Ce travail est réalisé en commun avec Paul Dorbec et Pascal Ochem (LRI).
Vendredi 18 février 2011 - Testing Planarity of Partially Embedded Graphs - Jan Kratochvil .
Résumé : We pose and study the following question: Given a (planar) graph G and a planar embedding of its subgraph H, can this be extended to a noncrossing embedding of the entire graph G? This approach follows the paradigm of completing a partial solution of a particular problem, which has been studied in many different situations before. Unlike in many cases, when the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas which show that planarity of partially embedded graphs performs the "oncas" behaviour - obvious necessary conditions for planarity are also sufficient. In particular, a 2-connected graph allows an extension of an embedding of its subgraph H if and only the skeleton of each node of its SPQR-tree has an embedding compatible with the given embedding of H. This implies that no dynamic programming is needed for a decision algorithm, the nodes of the SPQR-tree can be processed independently in parallel. It should be noted that though 2-connected graphs form the core situation, nontrivial steps are needed to handle the less connected cases. By refining the techniques and using appropriately adjusted data structures we manage to achieve a linear time algorithm.
On the other hand we consider several generalizations of the problem, e.g. minimizing the number of edges of the partial embedding that need to be rerouted, and argue that they already become NP-hard.
The talk is based on a joint paper with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vit Jelinek, Maurizio Patrignani, and Ignaz Rutter that was be presented at SODA 2010.
Vendredi 25 février 2011 - Session Problème .
Vendredi 4 mars 2011 - An algorithmic decomposition of claw-free graphs leading to an O (n^3)-algorithm for the weighted stable set problem - Gautier Stauffer.
Résumé:
We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in $O(n^3)$-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present paper. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is, on the other hand, algorithmic, i.e. it is coupled with an $O(n^3)-$time procedure that actually produces the decomposition. We also believe that our algorithmic decomposition result is interesting on its own and might be also useful to solve other kind of problems on claw-free graphs.
Vendredi 11 mars 2011 - Le "disjoint path problem" et le "minor containement problem" - Frédéric Mazoit .
Résumé :
Je présenterai un algorithme polynomial pour résoudre ces deux problèmes.
Vendredi 18 mars 2011 - Coloration d'arêtes à distance 2 - Hervé Hocquard.
Résumé : Une k-coloration d'arêtes à distance 2 (ou forte) d'un graphe est une coloration d'arêtes telle que deux arêtes adjacentes ou adjacentes à une même arête reçoivent des couleurs différentes. L'indice chromatique fort d'un graphe G est le nombre minimum de couleurs k tel que G admet une k-coloration forte d'arêtes. Dans cet exposé, la première partie sera consacrée à la majoration de l'indice chromatique fort pour certaines classes de graphes et dans la seconde partie nous présenterons des résultats de complexité (du problème de k-coloration forte d'arêtes) pour les graphes planaires. Ce travail a été réalisé en collaboration avec Pascal Ochem et Petru Valicov.
Vendredi 25 mars 2011 - Coloration d'arêtes à distance 2 (suite) - Petru Valicov.
Résumé : La suite de l'exposé d'Hervé Hocquard. Nous allons continuer la partie sur la complexité du problème de k-coloration forte d'arêtes ainsi que d'un problème voisin - le couplage induit. Un couplage induit d'un graphe G est un un ensemble d'arêtes M, tel que le sous-graphe de G induit par M est un couplage. Autrement dit, M est un couplage tel qu'il ne contient pas deux arêtes incidentes à une autre arête dans G.
C'est un travail réalisé avec Pascal Ochem et Hervé Hocquard.
Vendredi 1er avril 2011 - Décomposition de graphes - André Raspaud.
Résumé : A graph G is called improperly (d1, ... dk )-colorable, or just (d1, ... dk )-colorable, if the vertex set of G can be partitioned into subsets V1, ... Vk such that the graph G[Vi] induced by the vertices of Vi has maximum degree at most di for all 1 ≤ i ≤ k. This notion generalizes those of proper k-coloring (when d1 = ... = dk = 0) and d-improper k-coloring (when d1 = ... = dk = d ≥ 1).
Proper and d-improper colorings have been widely studied. As shown by Appel and Haken, every planar graph is 4-colorable, i.e. (0, 0, 0, 0)-colorable. Eaton and Hull and independently Skrekovski proved that every planar graph is 2-improperly 3-colorable (in fact, 2-improper choosable), i.e. (2,2,2)-colorable.
This latter result was extended by Havet and Sereni to not necessarily planar sparse graphs as follows: Theorem. For every k ≥ 0, every graph G with mad(G) < (4k+4)/(k+2) is k-improperly 2-colorable (in fact k-improperly 2-choosable), i.e. (k,k)-colorable.
We recall that mad(G) = {max(2|E(H)|/|V(H)|),H ⊆ G}, is the maximum average degree of a graph G.
In this talk we will present obtained results concerning the (k, j)-colorability for some values of k and j (k = j) for graphs with a given maximum average degree.
Vendredi 8 avril 2011 - Nowhere-zero flows on signed eulerian graphs - Martin Skoviera.
Resume : A signed graph is a graph in which every edge is labelled with a sign, +
or -. In the talk we introduce flows on signed graphs as a natural
analogue of flows on unsigned (that is, all-positive) graphs, based on the
use of bidirected rather than directed edges. After giving a brief survey
of known results about nowhere-zero flows on signed graphs we concentrate
on flows on signed eulerian graphs. We show that every signed eulerian
graph that has a nowhere-zero flow has a nowhere-zero 4-flow. This
indicates a significant difference from the unsigned case where every
eulerian graph is known to have a nowhere-zero 2-flow. We also
characterise those signed eulerian graphs whose flow number equals 2, 3,
and 4, respectively.
This is a joint work with Edita Macajova.
Vendredi 15 avril 2011 - Sur la difficulté de séparer un graphe par des plus courts chemins - Emilie DIOT.
Résumé : Les schémas de routage et de calcul de distances les plus efficaces sont conçus à partir de décompositions hiérarchiques de la topologie en plus courts chemins. Ces constructions sont calculables efficacement pour de nombreuses topologies, comme les graphes planaires par exemple. Dans cet exposé je montrerais cependant que la décomposition d'une topologie arbitraire en k plus courts chemins est NP-difficile.
Vendredi 29 avril 2011 - Bounding the identifying code number of a graph using its degree parameters, a probabilistic approach - Florent Foucaud.
Abstract : An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. Let M(G) denote the minimum size of an identifying code in G. It was conjectured recently that if G is connected, has n vertices and maximum degree d, M(G) <= n-n/d+O(1).
In a first part, we use Lovász' Local Lemma to give new upper bounds on M(G) for various classes of graphs in order to get closer to the conjectured bound than already known results.
In a second part, we use the first moment method to give improved bounds for graphs having given minimum degree and girth 5. Moreover we show that these bounds are asymptotically tight by computing the identifying code number of random d-regular graphs w.h.p. using the pairing model.
This is joint work with Guillem Perarnau (UPC, Barcelona).
Vendredi 13 mai 2011 - Rappels sur la méthode probabiliste en théorie des graphes - Paul Dorbec
Résumé :
La méthode probabiliste est un outil fréquemment utilisé en théorie des
graphes, qui permet parfois d'obtenir des résultats élégants avec des
preuves simples. Au cours de cet exposé, je vous rappellerai les
principes de ce qu'on appelle la méthode probabiliste, illustrés par une
série d'exemples dans différents domaines de la théorie des graphes.
Les résultats présentés peuvent être retrouvés dans les livres de
référence du domaine.
Vendredi 20 mai 2011 - Nowhere-zero flows in Cartesian bundles of graphs - Edita Rollova
Résumé :
A nowhere-zero k-flow on a graph G is an assignment of a direction and a non-zero integer in absolute value smaller than k to each edge of G in such a way that, for each vertex, the sum of incoming values equals the sum of outgoing values.
Our work continues and extends the study of nowhere-zero flows on product graphs initiated by Imrich and Skrekovski in 2003. hey proved that the Cartesian product of any two nontrivial connected graphs has a nowhere-zero 4-flow. Product graphs have been examined for many different graph properties because of their relatively simple structure and considerable generality. We have examined a natural (although lesser known) generalisation of the Cartesian product called Cartesian bundle.
By combining of flow methods with algebraic methods we will show that every Cartesian bundle of two graphs without isolated vertices has a nowhere-zero 4-flow.
This is a joint work with Martin Skoviera.
Vendredi 27 mai 2011 - 2-dipath and oriented L(2,1)-labelings of some families of oriented planar graphs - Sagnik Sen.
Résumé : To distinguish close and very close transmitters in a wireless communication system, Griggs and Yeh proposed a variation of the Frequency Assignment Problem (or simply FAP) by introducing the notion of L(2,1) labeling. A feature of this graph theoretic models for FAP was that, communication was assumed to be possible in both directions (duplex) between two radio transmitters and, therefore, these models were based on undirected graphs. But in reality, to model FAP on directed or oriented graphs could be interesting, was pointed by Aardal et al in their survey. There are two different L(2,1) labelings of oriented graphs, namely, 2-dipath L(2,1) labeling (that is, a vertex labeling with non negative integers, such that, the label difference for adjacent vertices is at least 2 and for vertices at directed distance 2 is at least 1) and oriented L(2,1) labeling (that is, a 2-dipath L(2,1) labeling which is also an oriented coloring).
In this talk, we have improved the existing bounds for 2-dipath and oriented L(2,1) span (the minimum possible "largest" value used for the respective labelings) for the class of planar graphs with girth 5, 11, 16, outerplanar, cactus, wheels and leaf independent Halin graphs.
Mardi 7 juin 2011, 11h à 12h30 - A Short History of the Theory of Preprocessing - Mike Fellows.
Résumé : The talk will survey the theory of preprocessing for NP-hard problems
that has emerged in recent years in the context of parameterized / multivariate
algorithmics. Some general techniques for obtaining small kernels in polynomial time
will be described, as well as new methods for obtaining lower bounds, recent results and
research frontiers.
Jeudi 9 juin 2011, 11h - Discussion sur les principaux thèmes de recherche dans le domaine des graphes, de leur structuration, de l'algorithmique correspondante - Animée par Bruno Courcelle.
APPEL à intervention:
Celles et ceux d'entre vous qui souhaitent présenter quelques thèmes de recherche FUTURE
(pas juste ce qu'ils/elles font actuellement) devraient contacter B. Courcelle pour qu'il puisse
coordonner les interventions ; ils/elles peuvent lui envoyer 2 ou 3 transparents PDF en format paysage).
Vendredi 10 juin 2011 - Computational Social Choice: Kemeny Scores and Parameterized Complexity - Frances Rosamond
Résumé : The multidisciplinary Consensus Problem: how independent agents reach a joint, collective decision, has applications in political resolution, but also important applications in Health (agreement on services), Image Processing (pixel value), Networks (agreement among processors), Auctions (agreement on bids), Search Engines (agreement on pages), among many others. The objects of study: opinions, rankings, observations, votes, gene sequences, sensor-networks in security systems or climate models, together with the presence of massive datasets, partial or uncertain information, distributed or interoperating decision makers, possibly over various time-frames, with the ability to share information at unprecedented speeds, make the Consensus Problem extremely complex.
Vendredi 24 juin 2011 - Minmax Degree of Graphs - Clément Charpentier .
Résumé : The minmax degree of a graph G is the largest integer m such
that every edge of G is incident with a vertex with degree at least m.
For some classes of graphs, bounds on minmax degree have some
consequences on edge-decomposition and game coloring number.
During this talk, we shall present some results and perspectives on
minmax degree.
Vendredi 1 juillet 2011 - The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes. - Seog-Jin Kim.
Résumé :
Let Cm be the cycle of length m. We denote the Cartesian product of
n copies of Cm by G(n, m) := Cm x Cm x · · · x Cm . The k-distance chromatic
number χk (G) of a graph G is χ(Gk ) where Gk is the kth power of the graph
G = (V, E) in which two distinct vertices are adjacent in Gk if and only if their
distance in G is at most k. The k-distance chromatic number of G(n, m) is
related to optimal codes over the ring of integers modulo m with minimum Lee
distance k + 1. In this paper, we consider χ2 (G(n, m)) for n = 3 and m ≥ 3. In
particular, we compute exact values of χ2 (G(3, m)) for 3 ≤ m ≤ 8 and m = 4k,
and upper bounds for m = 3k or m = 5k, for any positive integer k. We also
show that the maximal size of a code in Z3 with minimum Lee distance 3 is 26.
