Since december 2021, I am chargé de recherche CNRS at LIRMM in the AlGCo team. Between 2018 and 2021 I was doing a post doc in the Algorithms group at the University of Bergen.
Until July 2018 I was doing a PhD with Frédéric Havet in COATI and Stéphan Thomassé in MC2.

Contact me at william.lochet@gmail.com.

Research interests

I work on Theoretical Computer Science, where I mainly study graph algorithm and computational geometry.
From my PhD I also keep some interest in structural graph theory.

Publications

• Packing Short Cycles
  SODA 2025 With M. Bentert, F. Fomin, P. Golovach, T. Korhonnen, F. Panolan, M.S Ramanujan, S. Saurabh, K. Simonov.
• PTASes for Euclidean TSP with Unit Disk and Unit Square Neighborhoods
  SODA 2025 With S. Bandyapadhyay, K. Clinch, D. Lokshtanov, S. Saurabh and J. Xue.
• Uniform Polynomial Kernel for Deletion to $K_{2,p}$ Minor-Free Graphs
  ISAAC 2024 With R. Sharma.
• Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable
  SODA 2024 With S. Bandyapadhyay, D. Lokshtanov, S. Saurabh and J. Xue.
• Edge separators for graphs excluding a minor.
  The Electronic Journal of Combinatorics 2023. With G. Joret and M. Seweryn.
• FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
  SoCG 2023 With S. Bandyapadhyay and S. Saurabh.
• Minimum-Membership Geometric Set Cover, Revisited
  SoCG 2023 With S. Bandyapadhyay, S. Saurabh and J. Xue.
• True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs
  SoCG 2022 With S. Bandyapadhyay, D. Lokshtanov, S. Saurabh and J. Xue.
• How to Find a Good Explanation for Clustering?
  AAAI 2022 With S. Bandyapadhyay, F. Fomin, P. Golovach, N. Purohit and K. Simonov.
• Detours in Directed Graphs.
  STACS 2022, Journal of Computer and System Sciences 2023 With F. Fomin, P. Golovach, D. Sagunov, S. Saurabh and K. Simonov.
• Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs.
  SODA 2022 With S. Bandyapadhyay, D. Lokshtanov, S. Saurabh and J. Xue.
• Exploiting Dense Structures in Parameterized Complexity.
  STACS 2021 With D. Lokshtanov, S. Saurabh and M. Zehavi.
• Powers of paths in tournaments.
  Combinatorics, Probability and Computing 2021. With N. Draganić, F. Dross, J. Fox, A. Girão, F. Havet, D. Korándi, D. Munhá Correia, A. Scott and B. Sudakov.
• Packing and covering balls in graphs excluding a minor.
  Combinatorica 2021. With N. Bousquet, W. Cames Von Batenburg, L. Esperet, G. Joret, C. Muller and F. Pirot.
• Progress on the adjacent vertex distinguishing edge colouring conjecture.
  SIAM Journal of Discrete Mathematics 2021. With G. Joret.
• A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem.
  SODA 2021 Presentation.
• EPTAS for k-means Clustering of Affine Subspaces.
  SODA 2021 With E. Eiben F. Fomin, P. Golovach, F. Panolan and K. Siminov.
• The directed 2-linkage problem with length constraints.
  Theoretical Computer Science 2020. With J. Bang-Jensen, T. Bellitto and A. Yeo.
• A Polynomial Kernel for Paw-Free Editing.
  IPEC 2020 . With E. Eiben and S. Saurabh.
• Parameterized Complexity of Directed Spanner 2 Problems.
  IPEC 2020, Algorithmica 2022 . With F. Fomin, P. Golovach, P. Misra, S. Saurabh and R. Sharma.
• A Polynomial Kernel for Line Graph Editing.
  ESA 2020. With E. Eiben.
• Fault Tolerant Subgraphs with Applications in Kernelization.
  ITCS 2020. With D. Lokshtanov, P. Misra, S. Saurabh, R. Sharma and M. Zehavi.
• Exact and Approximate Digraph Bandwidth.
  FSTTCS 2019. With P. Jain, L. Kanesh, S. Saurabh and R. Sharma.
• Subdivisions in digraphs of large out-degree or large dichromatic number.
  The Electronic Journal of Combinatorics 2019. With P. Aboulker, N. Cohen, F. Havet, P. Moura and S. Thomassé.
• A proof of the Erdös-Sands-Sauer-Woodrow conjecture.
  Journal of Combinatorial Theory Series B 2019. With N. Bousquet and S. Thomassé.
• Immersion of transitive tournaments in digraphs with large minimum outdegree.
  Journal of Combinatorial Theory Series B 2019.
• Bispindles in strongly connected digraphs with large chromatic number.
  The Electronic Journal of Combinatorics 2018. With N. Cohen, F. Havet and R. Lopes.
• Equitable orientations of sparse uniform hypergraphs.
  The Electronic Journal of Combinatorics 2016. With N. Cohen.
• Subdivision of oriented cycles in digraphs with large chromatic number.
  Journal of Graph Theory 2018. With N. Cohen, F. Havet and N. Nisse.
• The structure of typical eye-free graphs and a Turán-type result for two weighted colours.
  Combinatorics, Probability and Computing 2017. With P. Keevash.

Prizes

• 2020 : Google Hash Code 12th
• 2019 : Prix Charles Delorme for best dissertation in Graphs.

Student supervision

• 2019 : co-supervising Antonin Dudermel (M1, ENS Lyon) with S. Saurabh.
• 2020 : co-supervising Sarah Houdaigoui (M2, ENS) with S. Saurabh.
• 2023 : co-supervising Hugo Jacob (M2, ENS Paris-Saclay) with C. Paul.

Doctoral supervision

• 2023 -- ongoing : Hugo Jacob, with C. Paul.

Community service

• Discrete Mathematics & Theoretical Computer Science :
  Section Editor
• Workshop on Parameterized Algorithms for Geometric Problems :
  Organizing committee
• IPEC 2021:
  Program committee
• Virtual meeting on Width Parameters:
  Invited lecture on the grid minor theorem and algorithmic applications slides
• Mcgill summer group on positional games :
  Invited lecture on entropy compression slides
• Frontiers of Parameterized Complexity:
  Invited presentation on the disjoint shortest paths problem video slides
• STACS 2014:
  Organizing team
• International Research School on Graph Limits:
  Organizing committee
• International Workshop on Graph Limits:
  Organizing committee