Le laboratoire Samovar accueille M. Julien Baste (Post-doc à l’université d’Ulm, en Allemagne) en Salle G08 pour une présentation intitulée « Hitting minors on bounded treewidth graphs »
Quand: le Jeudi 21 mars 2019 à 10h30
Où: Salle G08, à Télécom SudParis
Title: Hitting minors on bounded treewidth graphs
Abstract For a fixed collection of graphs F, the F-DELETION problem consists in, given a graph G and an integer k, decide whether there exists S, subset of V(G), with |S| <= k such that G-S does not contain any of the graphs in F as a minor. This NP-hard problem is a generalization of some well known graph problems as VERTEX COVER (F=K_2), FEEDBACK VERTEX SET (F=K_3), or VERTEX PLANARIZATION (F=K_5,K_3,3). We are interested in its parameterized complexity when the parameter is the treewidth of G, denoted by tw. Namely, the objective is to determine, for a fixed F, the (asymptotically) smallest function f_F: N -> N such that F-DELETION can be solved in time f_F(tw)*n^O(1) on n-vertex graphs. In this talk we will provide the basic definitions of parameterized complexity, motivate the problem, and then, review some of the lower and upper bounds on the function f_F for several instantiations of F. The presented results are joint work with Ignasi Sau and Dimitrios Thilikos and can be found in
Biographie:
Après avoir complété son master à l’ENS de Cachan, Julien Baste a effectué sa thèse à l’université de Montpellier encadré par Ignasi Sau et Dimitrios Thilikos. Thèse qu’il a soutenue en septembre 2017. Cette dernière était accompagnée de trois ans de monitorat. Il a ensuite eu l’opportunité d’enseigner à Sorbonne université dans le cadre d’un ATER pendant l’année universitaire 2017-2018. Il est désormais, depuis septembre 2018, en postdoc à l’université d’Ulm, en Allemagne.