Le GT Graphes et Optimisation (GO) du GdR-RO organisera cette année une journée thématique à l'Université Paris Dauphine le jeudi 15/6/2017. L'objectif de cette journée est de réunir les chercheurs des communautés de l'informatique et de la recherche operationelle qui travaillent sur les graphes et l'optimisation.
L'inscription pour cette journée est ouverte et gratuite. Cependant, afin de faciliter l'organisation, si vous voulez participer veuillez envoyer un mail aux organisateurs (Cédric Bentz et Michail Lampis) jusqu'au jeudi 8/6.
On aura le plaisir d'acueillir quatre orateurs invités: Olivier Hudry, Dimitris Fotakis, Yota Otachi, et Christophe Picouleau.
Nous invitons les jeunes chercheurs (doctorant(e)s, post-docs) dont la recherche porte autour dees graphes et de l'optimisation de proposer (en envoyant un mail à Cédric Bentz et Michail Lampis) un titre et résumé pour faire un exposé court de leurs travaux pendant cette journée thématique.
| Time | Speaker | Title |
|---|---|---|
| 10:00-10:30 | Accueil - Café | |
| 10:30-11:15 | Christophe Picouleau | d-bloqueurs optimaux de paramètres de graphes |
| 11:15-12:00 | Olivier Hudry | Petit tour d’horizon sur les codes identifiants dans les graphes sans jumeaux |
| 12:00-14:00 | Pause repas | |
| 14:00-14:45 | Dimitris Fotakis | On the Size and the Approximability of Minimum Temporally Connected Subgraphs |
| 14:45-15:30 | Yota Otachi | A Faster Parameterized Algorithm for Pseudoforest Deletion |
| 15:30-16:00 | Café | |
| 16:00-17:00 | Exposés Jeunes Chercheurs | |
| 16:00-16:20 | Mostafa Darwiche | Local Branching Heuristic applied to Graph Edit Distance problem |
| 16:20-16:40 | Sonia Cannas | Musical Graphs |
| 16:40-17:00 | Tom Denat | Etude de la complexité moyenne de l'algorithme du branch and bound pour le problème du stable |
Etant donné un graphe G, une opération s et un paramètre de graphes p, un d-bloqueur consiste à modifier G en G' en répétant l'opération s de sorte que p(G'), la valeur du paramètre pour G', soit diminuée de d unités par rapport à la valeur initiale p(G). Lorsque le nombre d'opérations s utilisées est minimal le d-bloqueur est dit optimal.
Nous fournirons certains résultats, tels que structure des d-bloqueurs optimaux ou complexité algorithmique des problèmes de décision associés, lorsque l'opération s consiste en la suppression d'un sommet ou la contraction d'une arête, et le paramètre p est le nombre chromatique, le nombre de stabilité ou la taille de la clique maximale. Les problèmes étant le plus souvent NP-difficiles nous nous intéresserons à certaines sous-classes de graphes, notamment les graphes parfaits et les graphes définis par l'absence d'un sous-graphe induit fixé.
Ces résultats ont été obtenus en collaboration avec O. Dinner, D. Paulusma et B. Ries
Soit G = (S, A) un graphe non orienté connexe et soit r un entier strictement positif. Pour tout sommet x de G, la boule B(x, r) centrée en x et de rayon r est l’ensemble des sommets de G à distance (au sens de la plus courte chaîne) au plus r de x : B(x, r) = {y sommet de G avec d(x, y) <= r}, où d est la distance habituelle dans les graphes.
Deux sommets distincts x et y sont dits r-jumeaux de G s’ils ont même boule : B(x, r) = B(y, r). Le graphe G est dit sans r-jumeaux s’il n’existe pas de sommets r-jumeaux dans G.
Un sous-ensemble C de S est appelé code r-identifiant de G si on a les deux propriétés suivantes : 1. pour tout sommet x de G, B(x, r) contient au moins un élément de C (propriété de couverture) 2. pour toute paire {x, y} de sommets distincts, l’intersection de B(x, r) et de C est distincte de l’intersection de B(y, r) et de C (propriété de séparation). Autrement dit, pour tout sommet x de G, l’ensemble des éléments de C à distance au plus r de x est non vide et est propre à x.
Il est facile de constater qu’un code r-identifiant existe dans G si et seulement si G est sans r-jumeaux (dans ce cas, S est un code r-identifiant de G). Le problème consiste alors à déterminer un code r-identifiant de cardinal minimum ; un tel code est dit optimal.
L’exposé présente certaines propriétés combinatoires des graphes sans r-jumeaux et des codes r-identifiants optimaux de tels graphes. On s’intéressera par exemple aux questions suivantes, pour lesquelles G désigne un graphe sans r-jumeaux à n sommets et C un code r-identifiant optimal de G : - quelle est la complexité de la détermination de C pour G donné ? - quels sont les cardinaux possibles de C en fonction de n ? - G possède-t-il des structures remarquables comme sous-graphes ? - comment C évolue-t-il si on ajoute ou retire un sommet ou une arête dans G ? - combien peut-il exister de codes r-identifiants optimaux de G ? etc.
We consider temporal graphs with discrete time labels and investigate the size and the approximability of minimum temporally connected spanning subgraphs. We present a family of minimally connected temporal graphs with $n$ vertices and $\Omega(n^2)$ edges, thus resolving an open question of (Kempe, Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal connectivity certificates. Next, we consider the problem of computing a minimum weight subset of temporal edges that preserve connectivity of a given temporal graph either from a given vertex r (r-MTC problem) or among all vertex pairs (MTC problem). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree and that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth. We also show that the best approximation ratio for MTC is at least $O(2^{\log^{1-\epsilon} n})$ and at most $O(\min\{n^{1+\epsilon}, (\Delta M)^{2/3+\epsilon}\})$, for any constant $\epsilon > 0$, where $M$ is the number of temporal edges and $\Delta$ is the maximum degree of the underlying graph. Furthermore, we prove that the unweighted version of MTC is APX-hard and that MTC is efficiently solvable in trees and $2$-approximable in cycles.
A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3^k n k^{O(1)}) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56^k n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n. (This is joint work with Hans L. Bodlaender and Hirotaka Ono. The conference version appeared in IPEC 2016.)