Welcome on my professional webpage! (Pour la version française cliquez ici.)
I am a permanent CNRS researcher (chargé de recherche) in the MC2 team at LIP.
My research topics are graph theory, graph algorithms, and combinatorics, in particular in structural graph theory, well-quasi-ordering, packing/covering dualities, parameterized complexity, algorithmic enumeration, and intersection graphs.
A listing of results about the Erdős-Pósa Property can be found on that page.
Contact
Publications
In conference proceedings
- Polynomial gap extensions of the Erdős-Pósa Theorem, with Dimitrios M. Thilikos
- An O(log OPT)-approximation for covering/packing minor models of θr, with Dimitris Chatzidimitriou, Ignasi Sau, and Dimitrios M. Thilikos
- Induced minors and well-quasi-ordering, with Jarosław Błasiok, Marcin Kamiński, and Théophile Trunck
- Packing and covering immersion models of planar subcubic graphs, with Archontia Giannopoulou, O-joung Kwon, and Dimitrios M. Thilikos
- Cutwidth: obstructions and algorithmic aspects, with Archontia Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos, and Marcin Wrochna
- IPEC 2016 (best paper award)
- doi
- arxiv
- bib
- Linear kernels for edge deletion problems to immersion-closed graph classes, with Archontia Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos, and Marcin Wrochna
- On the tractability of optimization problems in H-graphs, with Fedor V. Fomin and Petr Golovach
- A tight Erdős-Pósa function for planar minors, with Wouter Cames van Batenburg, Tony Huynh, and Gwenaël Joret
- Enumerating minimal dominating sets in triangle-free graphs, with Marthe Bonamy, Oscar Defrain, and Marc Heinrich
- Lean tree-cut decompositions: obstructions and algorithms, with Archontia Giannopoulou, O-joung Kwon, and Dimitrios M. Thilikos
- A lower bound for constant-size local certification, with Virginia Ardévol Martínez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, and Pegah Pournajafi
- SSS 2022 (best paper award)
- doi
- arxiv
- bib
- Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius, with Gaétan Berthe, Marin Bougeret, and Daniel Gonçalves
- Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time, with Gaétan Berthe, Marin Bougeret, and Daniel Gonçalves
- WG 2024
- Local certification of geometric graph classes, with Oscar Defrain, Louis Esperet, Aurélie Lagoutte, and Pat Morin
- Kick the cliques, with Gaétan Berthe, Marin Bougeret, and Daniel Gonçalves
In journals
- Low polynomial exclusion of planar graph patterns, with Dimitrios M. Thilikos
- Journal of Graph Theory (2015)
- arxiv
- bib
- An edge variant of the Erdős-Pósa property, with Ignasi Sau and Dimitrios M. Thilikos
- Discrete Mathematics (2016)
- arxiv
- bib
- Scattered packings of cycles, with Aistis Atminas and Marcin Kamiński
- Theoretical Computer Science (2016)
- arxiv
- bib
- Recent techniques and results on the Erdős-Pósa property, with Dimitrios M. Thilikos
- Discrete Applied Mathematics (2017)
- arxiv
- bib
- Minors in graphs of large θr-girth, with Dimitris Chatzidimitriou, Ignasi Sau, and Dimitrios M. Thilikos
- Well-quasi-ordering H-contraction-free graphs, with Marcin Kamiński, and Théophile Trunck
- Discrete Applied Mathematics (2017)
- arxiv
- bib
- Packing and covering immersion models of planar sub-cubic graphs, with Archontia Giannopoulou, O-joung Kwon, and Dimitrios M. Thilikos
- An O(log OPT)-approximation for covering/packing minor models of
θr, with Dimitris Chatzidimitriou, Ignasi Sau, and Dimitrios M. Thilikos
- Algorithmica (2017)
- arxiv
- bib
- Multigraphs without large bonds are wqo by
contraction, with Marcin Kamiński and Théophile Trunck
- Journal of Graph Theory (2017)
- arxiv
- bib
- Polynomial expansion and sublinear separators, with Louis Esperet
- Hitting minors, subdivisions, and immersions in tournaments
- A tight Erdős-Pósa function for wheel minors, with Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, and Ignasi Sau
- Cutwidth: obstructions and algorithmic aspects, with Archontia Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos, and Marcin Wrochna
- Induced minors and well-quasi-ordering, with Jarosław Błasiok, Marcin Kamiński, and Théophile Trunck
- A tight Erdős-Pósa function for planar minors, with Wouter Cames van Batenburg, Tony Huynh, and Gwenaël Joret
- On the tractability of optimization problems in H-graphs, with Fedor V. Fomin and Petr Golovach
- Enumerating minimal dominating sets in Kt-free graphs and variants, with Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Michał Pilipczuk
- Linear kernels for edge deletion problems to immersion-closed graph classes, with Archontia Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos, and Marcin Wrochna
- A Menger-like property of tree-cut width, with Archontia Giannopoulou, O-joung Kwon, and Dimitrios M. Thilikos
- Packing and covering induced subdivisions, with O-joung Kwon
- Twin-width and generalized coloring numbers, with Jan Dreier, Jakub Gajarsky, Yiting Jiang, and Patrice Ossona de Mendez
- Long induced paths in minor-closed graph classes and beyond, with Claire Hilaire
- A lower bound for constant-size local certification, with Virginia Ardévol Martínez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, and Pegah Pournajafi
- Sparse graphs without long induced paths, with Oscar Defrain
Popular science
- Beaux ordres et graphes (poster in french)
- presented at the event Journées nationales du GDR-IM (2016)
- hal
Code
From time to time I contribute to SageMath.
- phitigra, a visual graph editor for SageMath
- 2020-2022
- repository
- documentation
- part of SageMath's optional packages from version 9.6
- domenum, a python/sage implementation of the algorithm described in our article Enumerating minimal dominating sets in Kt-free graphs and variants (see above)
- 2018-2019
- part of SageMath since version 9.1
- source
- splitenum, a python/sage implemetation of the enumeration algorithm for minimal dominating sets in split graphs described by Kanté et al. in On the enumeration of minimal dominating sets and related notions. (doi, arxiv)
- 2018
- tarball
Student supervision
PhD student
- fall 2022-...: co-supervision of Gaétan Berthe (with Marin Bougeret and Daniel Gonçalves)
Internship
- spring 2020: supervision of the M1 internship of Hippolyte Lapendéry (University Clermont Auvergne)
Programming projects
At the University Clermont Auvergne / ISIMA:
- spring 2021: supervision of the Prep’ISIMA 2 programming project C2CtoPDF
- spring 2020: supervision of the Prep’ISIMA 2 programming project Lyapunov
- spring 2020: supervision of the Prep’ISIMA 2 programming project Space Billiard
At the University of Montpellier (Faculté des Sciences):
- spring 2016: supervision of Clément Daumet, Nicolas Theron, and Dorine Tabary for the programming project (TER L3) Growing trees by programming
- spring 2016: supervision of Mohamed Bareche, Jordan Ferrad, and Tianome Rasolohery programming project (TER L3) A shooter game with gravity
Teaching
At the University of Montpellier (Faculté des Sciences):
- 2015-2016, spring term: exercise sessions for the lecture Models of computation (HLIN203, L1, 33h)
- 2015-2016, fall term: computer lab sessions for the lecture Graph algorithms (HLIN501, L3, 16.5h)
- 2014-2015, spring term: computer lab sessions for the lecture Imperative programming (HLIN202, L1, 18h)
- 2014-2015, fall term: exercise/lab sessions for the lecture Introduction to algorithms and programming (HLIN101, L1, 24h and 27h)
Organizational duties
- 2020-2022: co-organizer of the local research seminar AlCoLoCo at LIMOS (with Florent Foucaud)
- 2022: head of the organizing commitee of the SGT summer school on structural graph theory (Murol, 7-10/06/2022)
- 2020-2022: co-organizer of the GRAA online seminar (with Louis Esperet, Nicolas Bousquet, and Rémi Watrigant)
- 2016: member of the organizing commitee of the days JCALM (Montpellier, 10-11/03/2016)
- 2015: member of the organizing commitee of the workshop GROW (Aussois, 11-15/10/2015)
Grants and projects
- 2022-present: member of the ANR JCJC Gralmeco project led by Florent Foucaud
- oct. 2017-june 2019: member of Stephan Kreutzer's ERC project Distruct
- 2014-2017: PI of the project Graphs within graphs funded by a PRELUDIUM grant from the Polish National Science Center
- 2013-2014: scholarship of the Warsaw Center of Mathematics and Computer Science
Previously
- Dec. 2019-Jan. 2024: chargé de recherches CNRS at LIMOS
- Oct. 2017-June 2019: postdoc at TU Berlin in the Logic and Semantics group, with Stephan Kreutzer
- Oct. 2013-Nov. 2016: PhD at the University of Warsaw and the University of Montpellier (cotutelle), supervised by Marcin Kamiński and Dimitrios M. Thilikos;
- Spring 2013: Master's thesis Extensions of the grid exclusion theorem prepared at LIRMM under the supervision of Dimitrios M. Thilikos
Links
My pages on ORCID, HAL, DBLP, and arxiv.
Last update: Summer 2024.