Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
Maximum Independent Set in H-free graphs
Edouard BONNET

05 October 2018, 14h30
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche : Théorie des graphes

Résumé :
Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1,3), the computational complexity of MIS is generally open except for a small number of cases.
We will explore the parameterized complexity of MIS in H-free graphs.
Our distant goal is to establish a dichotomy of the H for which the problem can be solved in time f(k)n^{O(1)} and the ones for which such an algorithm is unlikely to exist (where n is the total number of vertices, k is the size of the solution, and f is any computable function).
Recast in the parameterized complexity language, we want to know when the problem is FPT and when it is W[1]-complete.
We will present a selection of results and draw a parallel with the situation for the 'classical dichotomy' (P/NP-complete).

This is joint work with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant.

Pour en savoir plus :
Séminaires
Heterogeneous Treatment Effects Estimation: When M
Raisonnement automatique
Thursday 02 June 2022 - 10h30
Salle : 2011 - DIG-Moulon
Naoufal Acharki .............................................

Witness Generation for JSON Schema
Langages et systèmes centrés données
Monday 30 May 2022 - 00h00
Salle : 455 - PCRI-N
Mohamed-Amine BAAZIZI .............................................

TUTORIAL CODALAB - Apprenez à organiser un challen
Wednesday 13 April 2022 - 00h00
Salle : 1 - DIG-Moulon
Adrien Pavao .............................................

Generative Neural Networks for Observational Causa
Raisonnement automatique
Thursday 07 April 2022 - 10h30
Salle : 2011 - DIG-Moulon
Diviyan Kalainathan .............................................

Datamining in Epi- and Phylogenetics
Tuesday 15 March 2022 - 11h00
Salle : 455 - PCRI-N
Thomas Haschka .............................................