My research focuses on algorithmics, mainly for graph problems. Among others, I am interested in efficient algorithms for hard combinatorial problems: exact (parameterized) algorithms, approximation...
I participated in the organization of:
- École de Printemps en Informatique Théorique" (EPIT 2024), Aussois, May 13-17, 2024
- Journées Graphes et Algorithmes (JGA 2023) in Lyon, November 21-24, 2023
- Seymour is 70, 2020, 2021, 2022
- Journées Combinatoire-Graphes-Algo, 2018
- ICGT 2018
Students:
- Loïc Chassin de Kergommeaux: Ph.D (2024 - ...), co-supervised with Thomas Begin
- Malory Marin: Ph.D (2023 - ...), co-supervised with Nicolas Trotignon
- Loïc Chassin de Kergommeaux: M2 (2024), co-supervised with Thomas Begin, Anthony Busson, Malory Marin
- Sébastien Very: L3 (2024), co-supervised with Malory Marin
- Joachim Cendrier: M2 (2023), co-supervised with Thomas Begin, Anthony Busson
- Malory Marin: M2 (2023)
- Amir Nikabadi: M1 (2021)
- Charles Gassot: M2 (2020)
- Mathias Michel: M1 (2020)
- Thang Tran Xuan: M1 (2019), co-supervised with Édouard Bonnet, Stéphan Thomassé
- Diana Falamas: L3 (2018), co-supervised with Édouard Bonnet
- Thi Viet Ha Nguyen: M2 (2018)
Some other responsabilities:
- In charge of the Séminaire Graphes@Lyon
- Member of the jury of the Prix de thèse Gilles Kahn (2022, 2023, 2024)
- Member of the jury of the Prix de thèse Charles Delorme (2019, 2020, 2021, 2022)
Publications: (see also my DBLP)
- Channel allocation revisited through 1-extendability of graphs.
With Anthony Busson and Malory Marin. - Beyond recognizing well-covered graphs.
with Carl Feghali and Malory Marin. - Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width.
with Pierre Bergé, Édouard Bonnet and Hugues Déprés. - 1-Extendability of independent sets.
with Pierre Bergé, Anthony Busson and Carl Feghali.- IWOCA 2022 [Pre-print]
- Algorithmica 86(3): 757-781 (2024)
- Twin-width and polynomial kernels.
with Édouard Bonnet, Colin Geniet, Eun Jung Kim, Amadeus Reinald and Stéphan Thomassé. - Twin-width III: Max Independent Set, Min Dominating Set and Coloring.
with Édouard Bonnet, Colin Geniet, Eun Jung Kim and Stéphan Thomassé. - Twin-width II: small classes.
with Édouard Bonnet, Colin Geniet, Eun Jung Kim and Stéphan Thomassé. - Twin-width I: tractable FO model checking.
with Édouard Bonnet, Eun Jung Kim and Stéphan Thomassé.- FOCS 2020. [Pre-print]
- Journal of the ACM 69(1). 3:1-3:46 (2022)
- An algorithmic weakening of the Erdős-Hajnal conjecture.
with Édouard Bonnet, Stéphan Thomassé and Xuan Thang Tran. - Overlaying a hypergraph with a graph with bounded maximum degree.
with Frédéric Havet, Dorian Mazauric and Thi Viet Ha Nguyen.- CALDAM 2020, LNCS vol. 12016, 403-414.
- Discret. Appl. Math. 319: 394-406 (2022)
- When Maximum Stable Set can be solved in FPT time.
with Édouard Bonnet, Nicolas Bousquet and Stéphan Thomassé.- ISAAC 2019, LIPIcs vol. 149, 49:1-49:22. [Pre-Print]
- Comparing two clusterings using matchings between clusters of clusters.
with Frédéric Cazals, Dorian Mazauric and Romain Tetley.- ACM Journal of Experimental Algorithmics 24(1): 1.17:1-1.17:41. accepted. [Pre-Print]
- Constraint Generation Algorithm for the Minimum Connectivity Inference Problem.
with Édouard Bonnet and Diana-Elena Fălămaş.- SEA^2 2019, LNCS vol. 11544 167-183. [Pre-Print]
- Parameterized Complexity of Independent Set in H-Free Graphs.
with Édouard Bonnet, Nicolas Bousquet, Pierre Charbit and Stéphan Thomassé. - Complexity Dichotomies for the Minimum F-Overlay Problem.
with Nathann Cohen, Frédéric Havet, Dorian Mazauric and Ignasi Sau.- IWOCA 2017, LNCS 10765, pages 116-127. [Pre-Print]
- Journal of Discrete Algorithms, Vol. 52-53, Sept. 2018, pages 133-142 [Pre-Print]
- On the satisfiability of workflows with release points.
with Jason Crampton and Gregory Gutin.- SACMAT 2017, pages 207-217.[Pre-Print]
- Parameterized Resiliency Problems via Integer Linear Programming.
with Jason Crampton, Gregory Gutin and Martin Koutecký. - The Authorization Policy Existence Problem.
with Pierre Bergé, Jason Crampton and Gregory Gutin.- CODASPY 2017, pages 163-165 (short paper). [Pre-Print]
- The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency.
with Jason Crampton, Gregory Gutin and Daniel Karapetyan.- Journal of Computer Security, 25(1): 83-115, 2017. [Pre-Print]
- A Multivariate Approach for Testing Resiliency in Access Control.
with Jason Crampton and Gregory Gutin. - Resiliency Policies in Access Control Revisited.
with Jason Crampton and Gregory Gutin.- SACMAT 2016 (best paper award), Proceedings of SACMAT 2016, ACM, pp 101-111. [Pre-print]
- Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations.
with Marin Bougeret, Guillerme Duvillié and Rodolphe Giroudeau. - Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs.
with Nicolas Bousquet, Marin Bougeret and Rodolphe Giroudeau.- SOFSEM 2014, Springer LNCS 8327, pp. 150-161. [Pre-print]
- Approximating the Sparsest k-Subgraph in Chordal Graphs.
with Marin Bougeret and Rodolphe Giroudeau. - Sum-Max Graph Partitioning Problem.
with Marin Bougeret, Rodolphe Giroudeau and Jean-Claude König.
Theses:
- PhD thesis: Approximation et Complexité Paramétrée de Problèmes d'Optimisation dans les Graphes, under the direction of Rodolphe Giroudeau and Marin Bougeret. LIRMM, Montpellier, France. [PDF] (french)
- Master thesis: Bornes Inférieures pour la Kernelization, under the direction of Christophe Paul. LIRMM, Montpellier, France. [PDF] (french)