Since September 2023, I am a demi-ATER in the team CASH at the ENS Lyon in France.

- Algorithms, Complexity Theory and Parameterized Complexity Theory
- Graphs and Temporal Graphs
- Automata Theory and Formal Languages
- Type Theory
- OCaml

- Participation to Déclic 2023 on December 5th.
- Since September 2023, I am a demi-ATER in the team CASH working with Gabriel Radanne on Dowsing.
- Our team Zygosity ended up second at the PACE Challenge 2023 in the heuristic track
- Our paper Kernelizing Temporal Exploration Problems has been accepted from presentation at IPEC 2023.
- Our paper Cluster Editing with Overlapping Communities has been accepted from presentation at IPEC 2023.

- Kernelizing Temporal
Exploration Problems.

IPEC 2023 - PACE Solver Description:
Zygosity.

IPEC 2023 - Cluster Editing with
Overlapping Communities.

IPEC 2023 - Synchronization and Diversity of
Solutions.

AAAI 2023 - Multi-Parameter Analysis of
Finding Minors and Subgraphs in Edge Periodic
Temporal Graphs.

SOFSEM 2023 - On the Complexity of
Intersection Non-emptiness for Star-Free Language Classes.

FSTTCS 2021 - Diversity in Kemeny Rank
Aggregation: A Parameterized Approach.

IJCAI 2021 - Order Reconfiguration Under
Width Constraints.

MFCS 2021 - Three Is Enough for Steiner
Trees.

SEA 2021 - Width Notions for
Ordering-Related Problems.

FSTTCS 2020

- TA for Functional Project, ENS Lyon, Spring 2024
- TA for Theory of programming, ENS Lyon, Autum 2023
- TA for Algorithm 1, ENS Lyon, Autum 2023
- Lecturer for Parameterized Algoritms, University of Trier, Summer semester 2023
- TA for Parallel Programming, University of Bergen, Spring 2019

I work mainly with OCaml. All my work is publish under open source license.

- Dowsing: Tool to search functions in OCaml libraries by using their types as key.
- Mnemonicoeus: Prototype of memory dump analyser for OCaml.
- ARES: Help running timing experiments.
- Containers: A lightweight, modular standard library extension for OCaml.

**Supervisors:** Mateus de Oliveira Oliveira, Michael Fellows, Helwig Hauser

**Opponents:** Ana Shirley Ferreira da Silva, Vinícius Fernandes dos Santos

In the main body of this thesis, we study two different order theoretic problems. The first problem, called Completion of an Ordering, asks to extend a given finite partial order to a complete linear order while respecting some weight constraints. The second problem is an order reconfiguration problem under width constraints.

While the Completion of an Ordering problem is NP-complete, we show that it lies in FPT when parameterized by the interval width of ρ. This ordering problem can be used to model several ordering problems stemming from diverse application areas, such as graph drawing, computational social choice, and computer memory management. Each application yields a special partial order ρ. We also relate the interval width of ρ to parameterizations for these problems that have been studied earlier in the context of these applications, sometimes improving on parameterized algorithms that have been developed for these parameterizations before. This approach also gives some practical sub-exponential time algorithms for ordering problems.

In our second main result, we combine our parameterized approach with the paradigm of solution diversity. The idea of solution diversity is that instead of aiming at the de- velopment of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently di- verse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the so- lution space. There, we show that the considered diversity version of the Completion of an Ordering problem is fixed-parameter tractable with respect to natural para- maters that capture the notion of diversity and the notion of sufficiently good solutions. We apply this algorithm in the study of the Kemeny Rank Aggregation class of problems, a well-studied class of problems lying in the intersection of order theory and social choice theory.

Up to this point, we have been looking at problems where the goal is to find an optimal solution or a diverse set of good solutions. In the last part, we shift our focus from finding solutions to studying the solution space of a problem. There we consider the following order reconfiguration problem: Given a graph G together with linear orders τ and τ ′ of the vertices of G, can one transform τ into τ ′ by a sequence of swaps of adjacent elements in such a way that at each time step the resulting linear order has cutwidth (pathwidth) at most w? We show that this problem always has an affirmative answer when the input linear orders τ and τ ′ have cutwidth (pathwidth) at most w/2. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.

In addition to the main part of this work, we present results on two unrelated problems, namely on the Steiner Tree problem and on the Intersection Non-emptiness problem from automata theory.