Journée Graphes et Optimisation


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.

Inscription

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.

Orateurs Invités

On aura le plaisir d'acueillir quatre orateurs invités: Olivier Hudry, Dimitris Fotakis, Yota Otachi, et Christophe Picouleau.

Appel à Contributions

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.

Programme

La journée se tiendra à la salle B211 aile B, 2e étage de l'Univeristé Paris Dauphine (Comment s'y rendre).
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

Résumés

Christophe Picouleau

Titre : d-bloqueurs optimaux de paramètres de graphes
Résumé

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

Olivier Hudry

Titre : Petit tour d’horizon sur les codes identifiants dans les graphes sans jumeaux
Résumé

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.

Dimitris Fotakis

Titre : On the Size and the Approximability of Minimum Temporally Connected Subgraphs (arxiv)
Résumé

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.

Yota Otachi

Titre : A Faster Parameterized Algorithm for Pseudoforest Deletion (lipics)
Résumé

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.)