Nicolas Bousquet
|
|
|
|
|
nicolas DOT bousquet AT cnrs DOT fr |
CNRS Researcher, LIRIS, Lyon, France. |
Bureau H327 |
I defended my habilitation in Lyon the 3rd of July 2024 at 2pm. The manuscript can be found here and is entitled Journey on Configuration Graphs: Coloring and Independent Set Reconfiguration. The slides of the defense are there. My manuscript aims at giving an introduction to combinatorial reconfiguration and mentions many open problems in the field.
Formerly, I was an ATER (temporary assistant professor position) in Ecole Centrale de Lyon during the academic year 2015-2016. I was a member of the LIRIS laboratory in the GOAL (Graphes, AlgOrithmes et AppLications) team. Before, I was a postodoctoral fellow at the Department of Mathematics and Statistics at McGill University where I worked with Adrian Vetta. My scholarship was partially funded by the GERAD (Groupe d'études et de recherche en analyse des décisions) at Université de Montréal.
I have defended my PhD the 9-th of December 2013 under the direction of Stéphane Bessy and Stéphan Thomassé at the Université Montpellier 2 (LIRMM). Its title was "Hitting sets, VC-dimension and Multicut". The manuscript can be found there and the slides of the defense can be found there.
-->
Research interests
My topics of research include but are not limited to:
Projects
I am or was the PI or co-PI of the following projects
In 2019, I co-organized (with Marthe Bonamy), the third edition of the CoRe (Combinatorial Reconfiguration) workshop in Aussois (see here for more information).
Here is a list of current and former PhD students:
icon. To access to the slides of the presentations, click on the 
icon. When already available online, you can access to the paper on the editor webpage via the icon 
.
Short and local transformations between (Δ+1)-colorings, with Laurent Feuilloley, Marc Heinrich, Mikaël Rabie. Induced Minor Models. I. Structural Properties and Algorithmic Consequences, with Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, Nicolas Trotignon. Reconfiguration of Plane Trees in Convex Geometric Graphs, with Lucas de Meyer, Théo Pierron, Alexandra Wesolek. Renaming in distributed certification , with Louis Esperet, Laurent Feuilloley and Sébastien Zeitoun.
To appear in Theoretical Computer Science Shallow brambles, with Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, Piotr Micek. A subquadratic certification scheme for P5-free graphs, with Sébastien Zeitoun. Token Sliding on Graphs of Girth Five, with Valentin Bartier, Jihad Hanna, Amer Mouawad, Sebastian Siebertz. A note on locating sets in twin-free graphs, with Quentin Chuet, Victor Falgas-Ravry, Amaury Jacques, Laure Morelle. A note on highly connected K_{2,l}-minor free graphs, with Théo Pierron, Alexandra Wesolek, Discrete Mathematics: 114005 (2024).
Digraph redicolouring, with Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta and Amadeus Reinald, European Journal on Combinatorics : 116: 103876 (2024).
A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems, with Amer E. Mouawad, Naomi Nishimura and Sebastian Siebertz, Computer Science Reviews53, 100663 (2024).
Square coloring planar graphs with automatic discharging, with Lucas de Meyer, Quentin Deschamps, Théo Pierron, SIAM J. Discret. Math. 38(1): 504-528 (2024).
Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces, with Marthe Bonamy, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, Alex Scott. The smallest 5-chromatic tournament, with Thomas Bellitto, Adam Kabela and Théo Pierron. A note on the flip distance between non-crossing spanning trees, with Valentin Gledel, Jonathan Narboni, Théo Pierron. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint, with Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki and Kunihiro Wasa. Galactic Token Sliding, with Valentin Bartier and Amer Mouawad. Extremal Independent Set Reconfiguration, with Bastien Durain, Théo Pierron and Stéphan Thomassé. Improved square coloring of planar graphs, with Quentin Deschamps, Lucas de Meyer, Théo Pierron. Recolouring planar graphs of girth at least five, with Valentin Bartier, Carl Feghali, Marc Heinrich, Benjamin Moore and Théo Pierron. Locating-dominating sets: from graphs to oriented graphs, with Quentin Deschamps, Tuomo Lehtilä and Aline Parreau. A polynomial version of Cereceda's conjecture, with Marc Heinrich. Degeneracy of Pt-free and Ct-free graphs with no large complete bipartite subgraphs, with Marthe Bonamy, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak. Chordal directed graphs are not chi-bounded, with Pierre Aboulker and Rémi de Joannis de Verclos. EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs, with Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora and Stéphan Thomassé. Frozen (Delta+1)-colourings of bounded degree graphs, with Marthe Bonamy and Guillem Perarnau.
Graph Isomorphism for (H1,H2)-Free Graphs: An Almost Complete Dichotomy, with Marthe Bonamy, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron. On girth and the parameterized complexity of token sliding and token jumping, with Valentin Bartier, Clement Dallard, Kyle Lomer and Amer Mouawad. Recoloring graphs of treewidth 2, with Valentin Bartier and Marc Heinrich. Packing and covering balls in graphs excluding a minor, with Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet, Carole Muller, François Pirot. Parameterized Complexity of Independent Set in H-Free Graphs with Édouard Bonnet, Pierre Charbit, Stéphan Thomassé and Rémi Watrigant. A note on the simultaneous edge-coloring, with Bastien Durain. A proof of the Erdos-Sands-Sauer-Woodrow conjecture, with William Lochet and Stéphan Thomassé. Exact distance coloring in trees, with Louis Esperet, Ararat Harutyunyan and Rémi de Joannis de Verclos. On a conjecture of Mohar concerning Kempe equivalence, with Marthe Bonamy, Carl Feghali and Matthew Johnson. Multicut is FPT, with Jean Daligault and Stéphan Thomassé. Recoloring graphs via tree-decompositions, with Marthe Bonamy. Chi-bounded families of oriented graphs, with Pierre Aboulker, Jorgen Bang-Jensen, Pierre Charbit, Frédéric Havet, Frédéric Maffray and José Zamora. Decomposition techniques applied to the Clique-Stable set Separation problem, with Aurélie Lagoutte, Frédéric Maffray and Lucas Pastor.
A Vizing-like theorem for union vertex-distinguishing edge coloring, with Antoine Dailly, Eric Duchêne, Hamamache Kheddouci et Aline Parreau.
Colourful paths for 3-chromatic graphs, with Stéphane Bessy.
Fast recoloring of sparse graphs, with Guillem Perarnau.
The Erdos-Hajnal Conjecture for long holes and antiholes, with Marthe Bonamy and Stéphan Thomassé.
Identifying codes in hereditary classes of graphs and VC-dimension, with Aurélie Lagoutte, Zhentao Li, Aline Parreau and Stéphan Thomassé.
VC-dimension and Erdös-Pósa property, with Stéphan Thomassé.
The Erdos-Hajnal Conjecture for Paths and Antipaths, with Aurélie Lagoutte and Stéphan Thomassé.
Excluding cycles with a fixed number of chords, with Pierre Aboulker. 
]
Clique versus independent set, with Aurélie Lagoutte and Stéphan Thomassé. ]
Brooks' theorem on powers of graphs, with Marthe Bonamy. ]
Parameterized Domination in Circle Graphs, with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé. ]
Scott's induced subdivision conjecture for maximal triangle-free graphs, with Stéphan Thomassé.]
A Linear Kernel for Independent Set Reconfiguration in Planar Graphs, with Daniel W. Cranston. Complexity landscape for local certification, with , Laurent Feuilloley, Sébastien Zeitoun. The tape reconfiguration problem and its consequences for dominating set reconfiguration, with Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, Théo Pierron. How local constraints influence network diameter and applications to LCL generalizations, with Laurent Feuilloley, Théo Pierron. Reconfiguration of Plane Trees in Convex Geometric Graphs, with Lucas de Meyer, Théo Pierron, Alexandra Wesolek. Brief Announcement: Global certification via perfect hashing, with Laurent Feuilloley, Sébastien Zeitoun. Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters, with Laurent Feuilloley, Sébastien Zeitoun. Fast winning strategies for the attacker in eternal domination, with Guillaume Bagan, Nacim Oijid and Théo Pierron. Independent set reconfiguration in H-free graphs, with Valentin Bartier, Moritz Mühlenthaler. Parameterized Shortest Path Reconfiguration, with Kshitij Gajjar, Abhiruk Lahiri, Amer E. Mouawad. Metric dimension parameterized by treewidth in chordal graphs, with Quentin Deschamps and Aline Parreau. What can be certified compactly?, with Laurent Feuilloley and Théo Pierron. Galactic Token Sliding, with Valentin Bartier and Amer Mouawad. Token Sliding on graphs of girth give, with
Valentin Bartier, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint, with Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki and Kunihiro Wasa. Local certification of graph decompositions and applications to minor-free classes, with Laurent Feuilloley and Théo Pierron. Distributed recoloring of interval and chordal graphs, with Laurent Feuilloley, Marc Heinrich and Mikaël Rabie. (Sub)linear kernels for edge modification problems towards structured graph classes, with Gabriel Bathie and Théo Pierron. TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs, with Alice Joffard. Distributed algorithms for fractional coloring, with Louis Esperet and François Pirot. On girth and the parameterized complexity of token sliding and token jumping, with Valentin Bartier, Clement Dallard, Kyle Lomer and Amer Mouawad. Linear transformations between dominating sets in the TAR-model, with Alice Joffard, Paul Ouvrard. Reconfiguration of Spanning Trees with Many or Few Leaves, with Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki and Kunihiro Wasa, Approximating Sorting by reversals for trees, with Alice Joffard. Linear transformations between colorings in chordal graphs, with Valentin Bartier. When Maximum Stable Set can be solved in FPT time, with Edouard Bonnet, Stéphan Thomassé and Rémi Watrigant. The Perfect Matching Reconfiguration Problem, with Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kabayahi, Arnaud Mary, Moritz Mühlenthaler and Kunihiro Wasa. The distance between Matchings, with Tatsuhiko Hatanaka, Takehiro Ito and Moritz Mühlenthaler. EPTAS for Max Clique on Disks and Unit Balls, with Marthe Bonamy, Édouard Bonnet, Pierre Charbit and Stéphan Thomassé. Reconfiguration of graphs with connectivity constraints, with Arnaud Mary. Parameterized Complexity of Independent Set in H-Free Graphs, with Edouard Bonnet, Pierre Charbit, Stéphan Thomassé and Rémi Watrigant. Distributed coloring in sparse graphs with fewer colors, with Pierre Aboulker, Marthe Bonamy and Louis Esperet. Token Jumping in minor-closed classes, with Arnaud Mary and Aline Parreau. Token Sliding on Chordal Graphs, with Marthe Bonamy. Computing maximum cliques in B_2-EPG graphs, with Marc Heinrich. On the economic efficiency of the combinatorial clock auction, with Yang Cai, Christof Hunkenschroder and Adrian Vetta. Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Auction, with Yang Cai and Adrian Vetta. Coalition Games on Interaction Graphs: A Horticultural Perspective, with Zhentao Li and Adrian Vetta. A near-optimal mechanism for impartial selection, with Sergey Norin and Adrian Vetta. ]
Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs, with Marin Bougeret, Rodolphe Giroudeau and Rémi Watrigant. ]
Adjacent vertex-distinguishing edge coloring of graphs, with Marthe Bonamy and Hervé Hocquard. Recoloring bounded treewidth graphs, with Marthe Bonamy. ]
Parameterized Domination in Circle Graphs, with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé.]
Multicut is FPT, with Jean Daligault, Stéphan Thomassé.]
Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata, with Christof Löding.
]
A Polynomial Kernel for Multicut in Trees, with Jean Daligault, Stéphan Thomassé, Anders Yeo. ]
PasTEC - Exact solver for Cluster Editing, with Valentin Bartier, Gabriel Bathie, Marc Heinrich, Théo Pierron, Ulysse Prieto.
PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters. IPEC 2021, pp. 29:1-29:4. (Solver ranked 3rd in the Exact track of PACE 2021)
μSolver - Heuristic solver for Cluster Editing, with Valentin Bartier, Gabriel Bathie, Marc Heinrich, Théo Pierron, Ulysse Prieto. On the complexity of constrained reconfiguration and motion planning, with Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad, Naomi Nishimura, submitted.
A Note on the Complexity of Graph Recoloring, submitted.
Local certification of forbidden subgraphs, with Linda Cook, Laurent Feuilloley, Théo Pierron, Sébastien Zeitoun, submitted
Reconfiguration of independent sets in cographs, with Marthe Bonamy, preprint.
Local certification of MSO properties for bounded treedepth graphs, with Laurent Feuilloley and Théo Pierron. Surfaces have (asymptotic) dimension 2, with
Marthe Bonamy, Louis Esperet, Carla Groenland, François Pirot and Alex Scott. On the chromatic number of wheel-free graphs with no large bipartite graphs, with Stéphan Thomassé.
Shapley value on matching games for trees. Metric dimension on sparse graphs and its applications to zero forcing sets with Quentin Deschamps, Aline Parreau and Ignacio M. Pelayo. Hitting Sets: VC-dimension and Multicut. Le problème de l'équivalence pour les automates de Büchi fortement non ambigüs. ):
Recoloring, from statistical physics to combinatorics, One day Discrete Structure Meeting, ENS Lyon, June, 15th, 2018.
Exact distance coloring in trees, ANR DISTANCIA, Marseille, April, 11th, 2018.
Token Sliding on Chordal Graphs, BIRS Workshop, Banff, Canada, January 2017.
Discrete Maths and Optimization Seminar, McGill, September, 29th, 2014, Clique, stable sets and chromatic number.
Clermont-Ferrand, March, 28th, 2013, Hitting sets and VC-dimension.