We define pathographs, that is a generalization of graphs. Pathographs have vertices and edges, as graphs, but they also have « ur-path », that are special edges (that we will later subdivide). There are also spokes, that are adjacencies between vertices and ur-paths, and rungs, that are adjacencies between ur-paths. A realization of a pathograph G is any graph G' obtained from G be replacing each ur-path by a path of length at least 2. Furthermore, for each spoke v-p there must be at least one edge between v and the path P arising from the ur-path p, and for each rung pq, there must be at least one edge between the paths P, Q arising from p and q respectively. There are no other vertices or edges.

We consider the problem whose instance is a pathgraph G and a finite set of graphs F. The question is whether there exists a realization of G that contains no graph from F as an induced subgraph. We prove that this problem is undecidable (by reducing the Wang tiles problem to it). This result has several motivations. Pathographs are flexible enough to encode several graph containment problems. Some of them seems easy though it not known whether an algorithm exists for them, and our result show that this is not trivial. Also, many proofs in structural graph theory relies on a fact that some pathograph cannot be realized without introducing a forbidden induced subgraphs, so our result show that automatic provers for such lemmas do not exists in general.

This a joint work with Daniel Carter.

Les systèmes de contrôle de versions sont des outils qui permettent aux développeurs de suivre de l’évolution de leur code au cours de la durée de vie d’un projet. Ils permettent à plusieurs développeurs d’intéragir avec le code source simultanément et de garder trace de chaque version du projet.            Les premiers SCVs, tels que SCCS and RCS, étaient locaux et exclusifs: un seul utilisateur pouvait accéder au code à un moment donné grâce à un système de verrous. Les versions antérieures du code étaient accessibles, mais le processus était particulièrement lent. La seconde génération a permis de travailler sur plusieurs sites simultanément, en créant un dépôt central, depuis lequel les utilisateurs peuvent récupérer des versions ou en proposer de nouvelles.            Avec la troisième génération de SCVs, la notion de dépôt central et de version courante a disparu. À la place, chaque développeur a sa propre copie du dépôt, structurée comme un graphe de Merkle des versions qu’il connaît. Ainsi, chacun peut faire évoluer librement sa propre copie, en ajoutant des versions, créant de nouvelles branches ou en fusionnant d’autres. Ils peuvent aussi échanger leurs versions avec d’autres utilisateurs, en envoyant les versions qu’ils connaissent et en téléchargeant celles qu’ils ignorent.            Dans des projets d’envergure tels que Linux (Git) ou Firefox (Mercurial), ces opérations peuvent être coûteuses en temps : les dépôts peuvent contenir des millions de révisions, et plusieurs milliers peuvent être ajoutées chaque jour. À cette échelle, il devient nécessaire d’optimiser l’échange d’informations. Dans cet exposé, je présenterai nos travaux sur la découverte (déterminer efficacement quelles révisions deux agents ont en commun), les plages de données (un index cohérent qui permet de réaliser de la dichotomie partagée), et l’emploi des chaînes pour un test d’accessibité efficace.

Ces travaux ont été réalisés avec Laurent Bulteau (LIGM, CNRS), Pierre-Yves David (Octobus), et Euxane Tran-Girard (LIGM, Octobus).

In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomial-time algorithms. We specifically target radius (minimum eccentricity), diameter (maximum eccentricity), and all-eccentricity computations for which quadratic-time lower bounds are known under plausible conjectures. In each case, we introduce a notion of certificate as a specific set of nodes from which appropriate bounds on all eccentricities can be derived in subquadratic time when this set has sublinear size. The existence of small certificates for radius, diameter and all eccentricities is a barrier against SETH-based lower bounds for these problems. We indeed prove that for graph classes with certificates of bounded size, there exist randomized subquadratic-time algorithms for computing the radius, the diameter, and all eccentricities respectively. Moreover, these notions of certificates are tightly related to algorithms probing the graph through one-to-all distance queries and allow to explain the efficiency of practical radius and diameter algorithms from the literature.

In graph modification problems, we want to modify a graph through some operation (e.g. vertex/edge deletion/addition/contraction) to obtain a graph belonging to some specific class of graphs. Here, we pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. {\it IPEC}, 2024]. That is, we are interested in the parameter ${\rm I}_e(G)$, which, for a given graph $G$,
denotes the smallest $k \geq 0$ such that $G$ can be made locally irregular (\textit{i.e.}, with no two adjacent vertices having the same degree) by deleting $k$ edges. We exhibit notable properties of interest of the parameter ${\rm I}_e$, in general and for particular classes of graphs. Our investigation leads us to propose a conjecture that $\ie(G)$ should always be at most $\frac{1}{3}m+c$, where $m$ is the size of the graph $G$ and $c$ is some constant. We verify this conjecture in the case of paths, cycles, trees and complete graphs, and we provide the first step towards proving the conjecture for cubic graphs. Finally, we present a linear-time algorithm that computes $\ie(G)$ when $G$ is a tree of bounded maximum degree.

A total coloring of a graph G is an assignment of colors to the vertices and edges of G such that adjacent vertices or edges receive different colors, and each vertex has a different color from its incident edges. Determining the minimum number of colors required for a total coloring of a graph, known as the total chromatic number, plays a fundamental role in the total coloring problem. Currently, its main conjecture, called the Total Coloring Conjecture, has remained open for almost 60 years and has inspired the development of various coloring variants of this problem. In this talk, several open problems arising from the total coloring problem will be presented. A joint work with Mauro Nigro.

The goal of circular seriation is, given a set X and a dissimilarity d on X (we can see d as a complete valued graph on X, or as a distance (without the triangular inequality)), to determinate if X can be represented on a circle in a a way which is ‘’compatible’’ with d. There exist 4 non-equivalent definitions of this problem. We will present these four definitions and a simple and optimal algorithm for the two most interesting ones, at least in the ‘’strict’’ case (the inequalities that defines the problems are strict).

Roditty and Vassilevska-Williams [STOC 2013] showed that computing the diameter, i.e., farthest distance between any two vertices, of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Strong Exponential Time Hypothesis fails. In a breakthrough work, Cabello [TALG 2019] showed a subquadratic algorithm in planar graphs. Building upon a line of research on distance profiles, Le and Wulff-Nilsen [SODA 2024] presented a O(n^{2-c_h})-time algorithm for diameter in K_h-minor-free graphs, where c_h = theta(1/h). However, known lower bounds do not refute the possibility of an O_h(n^{2-c})-time algorithm in K_h-minor-free graphs for some universal constant c (not depending on h). We present such an algorithm for the case of bounded Euler genus graphs (and c=0.04) and discuss where our approach fails for the general excluded-minor case.

Joint work with Kacper Kluk, Marcin Pilipczuk, and Michał Pilipczuk.

This research aims to connect two important areas: parameterized complexity and multi-objective optimization. Parameterized complexity is a way of studying how efficiently an algorithm can solve a problem by focusing on given parameters, while multi-objective optimization focuses on real-world problems that have several goals to achieve at once. The Multi-Objective Traveling Salesman Problem (MOTSP) is a variation of the Traveling Sales-man Problem (TSP) where a salesman must visit a set of cities and return to the starting point, but instead of optimizing just one objective (like minimizing distance), there are multiple objectives to consider simultaneously. These objectives could be things like minimizing total cost, distance, or travel time, while also considering factors like fuel consumption or safety. We aim to solve MOTSP using a local search method. To enhance the effectiveness of this approach, we have proposed a new neighborhood operator. The Local MOTSP(r-swap) problem takes as input an H-ordered graph G = (V, E), two edge weight functions w1, w2 with maximum weight W, and a positive integer k. The goal is to determine whether there exists an ordered sequence S of at most k r-swaps such that perm(S) results in an improved Hamiltonian cycle. The problem is parameterized by r, k and W. We show that even with multiple objectives, the problem can still be solved in FPT time, specifically in time O(k2·k!·r2(k−1)·n + k5·r ·W4·n2).

In this talk, we present exact characterizations of the functions that are computable in anonymous networks with varying assumptions in the degree of awareness or control that agents have over their outneighbors. First, we characterize the computable functions in the “blind broadcast” model, i.e., when agents have no information on their outgoing neighborhoods. Then we enrich this communication model with either output port awareness, bidirectional channels, or outdegree awareness: In each case, we prove that a function can be computed if and only it is frequency-based, namely, its value only depends on the frequencies of the different input values. This characterization holds for both exact and approximate computability. If one or several nodes are distinguished as leaders, or if the cardinality of the network is known, then under any of the above three assumptions it becomes possible to compute any symmetric function.

Given a graph G, a proper k-colouring of G is said to be conflict-free if, for every non-isolated vertex v ∈ V(G), there is a colour with a unique occurrence in N(v). The pcf-chromatic number of G, denoted χ_{pcf}(G), is the minimum k such that a proper conflict-free (pcf for short) k-colouring of G exists. A weakening of the notion of pcf colourings exists, where one replaces “unique occurrence” with “odd number of occurrences”; those are called odd colourings, and the related chromatic parameter is denoted χ_o(G). Recently, Caro, Petruševski, and Škrekovski formulated two conjectures on the pcf and odd chromatic numbers of graphs of maximum degree Δ ≥ 3. They conjectured that χ_{pcf}(G) ≤ Δ+1 (pcf colouring conjecture), and the weaker statement that χ_o(G) ≤ Δ+1 (odd colouring conjecture). In the first part of this presentation, I will show how a probabilistic analysis of a random colouring of G drawn uniformly from the set of proper k-colouring of G — or a well-chosen subset thereof — yields an asymptotic version of the odd colouring conjecture, namely χ_o(G) ≤ Δ+O(lnΔ) as Δ→∞. I will then discuss how to adapt this to obtain stronger results when it moreover holds that the minimum degree of G is large enough. I will finish this presentation with a sketch of the proof of an asymptotic version of the pcf colouring conjecture, namely χpcf(G)≤Δ+O(lnΔ) as Δ→∞.

In directed graphs, a cycle can be seen as a structure that allows its vertices to loop back to themselves, or as a structure that allows pairs of vertices to reach each other through distinct paths. We extend these concepts to temporal graph theory, resulting in multiple interesting definitions of a “temporal cycle”. For each of these, we consider the problems of Cycle Detection and Acyclic Temporization. For the former, we are given an input temporal digraph, and we want to decide whether it contains a temporal cycle. Regarding the latter, for a given input (static) digraph, we want to time the arcs such that no temporal cycle exists in the resulting temporal digraph. We're also interested in Acyclic Temporization where the lifetime of the resulting temporal digraph is bounded. Multiple results are presented, including polynomial and fixed parameter tractable search algorithms, polynomial-time reductions from 3-SAT and Not All Equal 3-SAT, and temporizations resulting from arbitrary vertex orderings which cover (almost) all cases. 

Back in 1939, Frucht proved that every finite group is isomorphic to the automorphism group of a finite graph. This incited an examination of the influence that standard graph theoretical concepts can have on automorphism groups. Eventually, the framework was enlarged by extending the analyses to endomorphism monoids. This has ultimately established a particular connection between semigroup classes and graph classes, notably in terms of sparsity and combinatorial regularity. The goal of the presentation is to contextualize a new result on endomorphism monoids of regular graphs that adds some detail to the picture. This is joint work with Kolja Knauer.

We investigate the structure of graphs of twin-width at most 1 and uncover nice relations with several classical classes of hereditary graphs. An important finding is that they are permutation graphs and that their permutation diagrams and contraction sequences are closely related. We use these combinatorial tools to establish a recursive decomposition theorem for twin-width 1 graphs, and deduce a simple recognition algorithm running in linear time.

Joint work with Jungho Ahn, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht.

Tutte proposed integer flows when he studied the well-known 4-Color Problem. For studying the flow properties further, Jaeger et al. introduced the concept of group connectivity as a nonhomogeneous analogue of integer flows, and Goddyn et al. proposed the definition of circular flows which extends the range of flows to arbitrary rational numbers. In this talk, we will discuss the existence of circular flow for regular Class $I$ graphs and the equivalence of group connectivity on non-isomorphic groups with the same order.

Joint work with Jiaao Li and Meiling Wang.