{"id":1176,"date":"2019-03-11T12:12:00","date_gmt":"2019-03-11T11:12:00","guid":{"rendered":"https:\/\/samovar2022.int-evry.fr\/index.php\/2019\/03\/11\/seminaire-methodes-presente-par-julien-baste-le-21-03-19-a-10h30-en-g08\/"},"modified":"2020-09-04T18:45:19","modified_gmt":"2020-09-04T16:45:19","slug":"seminaire-methodes-presente-par-julien-baste-le-21-03-19-a-10h30-en-g08","status":"publish","type":"post","link":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/2019\/03\/11\/seminaire-methodes-presente-par-julien-baste-le-21-03-19-a-10h30-en-g08\/","title":{"rendered":"S\u00e9minaire Methodes pr\u00e9sent\u00e9 par Julien Baste le 21\/03\/19 \u00e0 10h30 en G08"},"content":{"rendered":"<p>Le laboratoire Samovar accueille <strong>M. Julien Baste<\/strong> (Post-doc \u00e0 l\u2019universit\u00e9 d\u2019Ulm, en Allemagne) en Salle G08 pour une pr\u00e9sentation intitul\u00e9e \u00ab\u00a0Hitting minors on bounded treewidth graphs\u00a0\u00bb<\/p>\n<p><strong>Quand:<\/strong> le Jeudi 21 mars 2019 \u00e0 10h30<br \/>\n<strong>O\u00f9:<\/strong> Salle G08, \u00e0 T\u00e9l\u00e9com SudParis<\/p>\n<p><strong>Title<\/strong>: Hitting minors on bounded treewidth graphs<\/p>\n<p>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=<em>K_2<\/em>), FEEDBACK VERTEX SET (F=<em>K_3<\/em>), or VERTEX PLANARIZATION (F=<em>K_5,K_<em>3,3<\/strong>). 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^<em>O(1)<\/em> 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 <https:\/\/arxiv.org\/abs\/1704.07284>.<\/p>\n<p><strong>Biographie:<\/strong><br \/>\nApr\u00e8s avoir compl\u00e9t\u00e9 son master \u00e0 l\u2019ENS de Cachan, Julien Baste a effectu\u00e9 sa th\u00e8se \u00e0 l\u2019universit\u00e9 de Montpellier encadr\u00e9 par Ignasi Sau et Dimitrios Thilikos. Th\u00e8se qu&rsquo;il a soutenue en septembre 2017. Cette derni\u00e8re \u00e9tait accompagn\u00e9e de trois ans de monitorat. Il a ensuite eu l\u2019opportunit\u00e9 d\u2019enseigner \u00e0 Sorbonne universit\u00e9 dans le cadre d\u2019un ATER pendant l\u2019ann\u00e9e universitaire 2017-2018. Il est d\u00e9sormais, depuis septembre 2018, en postdoc \u00e0 l\u2019universit\u00e9 d\u2019Ulm, en Allemagne.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Le laboratoire Samovar accueille M. Julien Baste (Post-doc \u00e0 l\u2019universit\u00e9 d\u2019Ulm, en Allemagne) en Salle G08 pour une pr\u00e9sentation intitul\u00e9e \u00ab\u00a0Hitting minors on bounded treewidth graphs\u00a0\u00bb Quand: le Jeudi 21 mars 2019 \u00e0 10h30 O\u00f9: Salle G08, \u00e0 T\u00e9l\u00e9com SudParis Title: Hitting minors on bounded treewidth graphs Abstract For a fixed collection of graphs F, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":1175,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ocean_post_layout":"","ocean_both_sidebars_style":"","ocean_both_sidebars_content_width":0,"ocean_both_sidebars_sidebars_width":0,"ocean_sidebar":"","ocean_second_sidebar":"","ocean_disable_margins":"enable","ocean_add_body_class":"","ocean_shortcode_before_top_bar":"","ocean_shortcode_after_top_bar":"","ocean_shortcode_before_header":"","ocean_shortcode_after_header":"","ocean_has_shortcode":"","ocean_shortcode_after_title":"","ocean_shortcode_before_footer_widgets":"","ocean_shortcode_after_footer_widgets":"","ocean_shortcode_before_footer_bottom":"","ocean_shortcode_after_footer_bottom":"","ocean_display_top_bar":"default","ocean_display_header":"default","ocean_header_style":"","ocean_center_header_left_menu":"","ocean_custom_header_template":"","ocean_custom_logo":0,"ocean_custom_retina_logo":0,"ocean_custom_logo_max_width":0,"ocean_custom_logo_tablet_max_width":0,"ocean_custom_logo_mobile_max_width":0,"ocean_custom_logo_max_height":0,"ocean_custom_logo_tablet_max_height":0,"ocean_custom_logo_mobile_max_height":0,"ocean_header_custom_menu":"","ocean_menu_typo_font_family":"","ocean_menu_typo_font_subset":"","ocean_menu_typo_font_size":0,"ocean_menu_typo_font_size_tablet":0,"ocean_menu_typo_font_size_mobile":0,"ocean_menu_typo_font_size_unit":"px","ocean_menu_typo_font_weight":"","ocean_menu_typo_font_weight_tablet":"","ocean_menu_typo_font_weight_mobile":"","ocean_menu_typo_transform":"","ocean_menu_typo_transform_tablet":"","ocean_menu_typo_transform_mobile":"","ocean_menu_typo_line_height":0,"ocean_menu_typo_line_height_tablet":0,"ocean_menu_typo_line_height_mobile":0,"ocean_menu_typo_line_height_unit":"","ocean_menu_typo_spacing":0,"ocean_menu_typo_spacing_tablet":0,"ocean_menu_typo_spacing_mobile":0,"ocean_menu_typo_spacing_unit":"","ocean_menu_link_color":"","ocean_menu_link_color_hover":"","ocean_menu_link_color_active":"","ocean_menu_link_background":"","ocean_menu_link_hover_background":"","ocean_menu_link_active_background":"","ocean_menu_social_links_bg":"","ocean_menu_social_hover_links_bg":"","ocean_menu_social_links_color":"","ocean_menu_social_hover_links_color":"","ocean_disable_title":"default","ocean_disable_heading":"default","ocean_post_title":"","ocean_post_subheading":"","ocean_post_title_style":"","ocean_post_title_background_color":"","ocean_post_title_background":0,"ocean_post_title_bg_image_position":"","ocean_post_title_bg_image_attachment":"","ocean_post_title_bg_image_repeat":"","ocean_post_title_bg_image_size":"","ocean_post_title_height":0,"ocean_post_title_bg_overlay":0.5,"ocean_post_title_bg_overlay_color":"","ocean_disable_breadcrumbs":"default","ocean_breadcrumbs_color":"","ocean_breadcrumbs_separator_color":"","ocean_breadcrumbs_links_color":"","ocean_breadcrumbs_links_hover_color":"","ocean_display_footer_widgets":"default","ocean_display_footer_bottom":"default","ocean_custom_footer_template":"","ocean_post_oembed":"","ocean_post_self_hosted_media":"","ocean_post_video_embed":"","ocean_link_format":"","ocean_link_format_target":"self","ocean_quote_format":"","ocean_quote_format_link":"post","ocean_gallery_link_images":"on","ocean_gallery_id":[],"footnotes":""},"categories":[294],"tags":[],"class_list":["post-1176","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-seminaires-2019-methodes-fr","entry","has-media"],"_links":{"self":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/1176","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/comments?post=1176"}],"version-history":[{"count":1,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/1176\/revisions"}],"predecessor-version":[{"id":1467,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/1176\/revisions\/1467"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/media\/1175"}],"wp:attachment":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/media?parent=1176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/categories?post=1176"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/tags?post=1176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}