Rémi Watrigant

Université Claude Bernard Lyon 1

• Home
• Research
• Teaching
• CV
• Contact

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:

• Malory Marin: Ph.D (2023 - ...)
• Loïc Chassin de Kergommeaux: M2 (2024)
• Sébastien Very: L3 (2024)
• Joachim Cendrier: M2 (2023)
• Malory Marin: M2 (2023)
• Amir Nikabadi: M1 (2021)
• Charles Gassot: M2 (2020)
• Mathias Michel: M1 (2020)
• Thang Tran Xuan: M1 (2019)
• Diana Falamas: L3 (2018)
• 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)

• Beyond recognizing well-covered graphs.
  with Carl Feghali and Malory Marin.
  • WG 2024 [Pre-print]
• Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width.
  with Pierre Bergé, Édouard Bonnet and Hugues Déprés.
  • STACS 2023 [Pre-print]
• 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é.
  • IPEC 2021 [Pre-print]
  • Algorithmica 84(11): 3300-3337 (2022)
• Twin-width III: Max Independent Set, Min Dominating Set and Coloring.
  with Édouard Bonnet, Colin Geniet, Eun Jung Kim and Stéphan Thomassé.
  • ICALP 2021 [Pre-print]
• Twin-width II: small classes.
  with Édouard Bonnet, Colin Geniet, Eun Jung Kim and Stéphan Thomassé.
  • SODA 2021. [Pre-print]
  • Combinatorial Theory, 2022.
• 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.
  • ESA 2020, LIPIcs 23:1-23:18. [Pre-print]
• 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é.
  • IPEC 2018, LIPIcs vol. 115, 2019, pages 17:1-17-13. [Pre-Print]
  • Algorithmica 82(8): 2360-2394 (2020)
• 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ý.
  • CIAC 2017, LNCS 10236, pages 164-176. [Pre-Print]
  • Theoretical Computer Science 795: 478-491 (2019)
• 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.
  • AAIM 2016, Springer LNCS 9778, pp. 173-184. [Pre-print]
• 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.
  • Discrete Mathematics & Computer Science, 19(4), 2017.
  • FCT 2015, Springer LNCS 9210, pp. 189-201. [Pre-print]
• 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.
  • Theory of Computing Systems, 58(1), pp. 111-132, 2016.
  • WAOA 2013, Springer LNCS 8447, pp. 73-84. [Pre-print]
• Sum-Max Graph Partitioning Problem.
  with Marin Bougeret, Rodolphe Giroudeau and Jean-Claude König.
  • Theoretical Computer Science, 540-541 pp. 143-155, 2014.
  • ISCO 2012, Springer LNCS 7422 pp. 297-308 [Pre-print]

---

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)

---