Welcome on my professional webpage! (Pour la version française cliquez ici.)
Since December 2019 I am a permanent CNRS researcher (chargé de recherche) in the LIMOS lab.
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
Manuscripts
- Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection
graphs of segments, with Gaétan Berthe, Marin Bougeret, and Daniel Gonçalves
- arxiv
- submitted in 2023
- Sparse graphs without long induced paths, with Oscar Defrain
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
In journals
- Low polynomial exclusion of planar graph patterns, with Dimitrios M. Thilikos
- An edge variant of the Erdős-Pósa property, with Ignasi Sau and Dimitrios M. Thilikos
- Scattered packings of cycles, with Aistis Atminas and Marcin Kamiński
- Recent techniques and results on the Erdős-Pósa property, with Dimitrios M. Thilikos
- 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
- 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
- Multigraphs without large bonds are wqo by contraction, with Marcin Kamiński and Théophile Trunck
- 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 Aboulkers, 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
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
Previously to my current position I was working or studying at the following places:
- 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 2023.