A temporal graph is an undirected graph G = (V,E) along with a function that assigns a time-label to each edge in E. A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum number of edges of a temporal path from u to v. A temporal alfa-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V, up to a multiplicative stretch factor of alfa. The size of H is measured as the number of its edges. In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k-1)-spanner with \tilde{O}(kn^{1+1/k}) edges, where k > 1 is an integer parameter of choice and n is the number of nodes in G. Choosing k = log n, we obtain a temporal O(log n)-spanner with \tilde{O}(n) edges that has almost the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] to preserve temporal connectivity. We then turn our attention to general temporal graphs. Since \Omega(n^2) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that \tilde{O}(n/log(1+epsilon)) edges suffice to obtain a stretch of (1+epsilon), for any small epsilon > 0. This result is essentially tight in the following sense: there are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use \Omega(n^2) edges.

Link streams offer a good model for representing interactions over time. They consist of links (b,e,u,v), where u and v are vertices interacting during the whole time interval [b,e]. In this talk, we deal with the problem of enumerating maximal cliques in link streams. A clique is a pair (C,[t0,t1]), where C is a set of vertices that all interact pairwise during the full interval [t0,t1]. It is maximal when neither its set of vertices nor its time interval can be increased. Some of the main works solving this problem are based on the famous Bron-Kerbosch algorithm for enumerating maximal cliques in graphs. We take this idea as a starting point to propose a new algorithm which matches the cliques of the instantaneous graphs formed by links existing at a given time to the maximal cliques of the link stream. We compute its complexity, which is better than the state-of-the art ones in many cases of interest. We also study the output-sensitive complexity, which is close to the output size, thereby showing that our algorithm is efficient. To confirm this, we perform experiments on link streams used in the state of the art, and on massive link streams, up to 100 million links. In all cases our algorithm is faster, mostly by a factor of at least 10 and up to a factor of 10^4. Moreover, it scales to massive link streams for which the existing algorithms are not able to provide the solution. For more details, please consult the following paper: https://arxiv.org/abs/2302.00360.

We consider the context of a network modeled by an undirected graph where the edges are known, but not the connections between these edges. This can happen in old buildings where, for example, an electrical, gas or water network has not been documented and where the network is not easily accessible. We may have access to some cables or pipes of the network either because they are visible or because it is possible to probe the building to find them. From the edges of the graph, we obtain measures of the probability that two edges are incident, in other words measures of the linegraph of the network, with possibly errors in the measurements. We aim to correct the errors by finding the linegraph closest to the measurement graph. This problem is modeled as an edit distance problem in terms of deleting and adding edges in a graph to retrieve a linegraph. We pose the question, firstly, of studying the complexity of correcting these errors and its parameterized complexity with respect to the number of possible errors and the treewidth of the graph, secondly, the relevance of such correction in relation to the desired graph based on the number of measurement errors, and thirdly, what other information could be added to the graph to aid in reconstruction as the number of measurement errors increases.

A graph G is Hamiltonian if it exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G − S is at most |S| / t.

In 1973, Chvàtal conjecture the following : There exists a constant t such that every t-tough graphs is Hamiltonian.

Let t be a positive integer. A graph G with degree sequence d_1,d_2,…,d_n is P(t) (t being a positive integer) If for all i, t ≤ i <n/2, d_i ≤ i ⇒ d_{n−i+t} ≥ n−i. In 1995, Hoàng conjecture the following : If G is t-tough and P(t) then G is Hamiltonian. Hoàng prove that it is true for t ≤ 3. In 2023, Hoang and Robin proved that it is also true for t ≤ 4 by extending the Closure Lemma due to Bondy and Chvàtal into a version for tough graphs.

We prove that it is true for t≤7 for n large enough. To do so, we prove a lemma about covering some vertices of a graph with a bounded number of paths.

This is joint work with Chình T. Hoàng and Paul Dorbec.

We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words, we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here two relaxations of Clique: s-Club, in which the relaxation is focused on the distances in the cluster, and gamma-Complete-Subgraph in which the relaxation is made on the minimal degree in the cluster. As these two problems are known to be NP-hard, we study here their parameterized complexities. We prove that s-Club is NP-hard even restricted to graphs of degeneracy 3 whenever $s \ge 3$, which is a strictly stronger result than its W[1]-hardness parameterized by the degeneracy. Concerning gamma-Complete-Subgraph, we prove that it is W[1]-hard parameterized both by the degeneracy, implying the W[1]-hardness parameterized by the number of vertices in the \gamma-complete-subgraph, and by the number of vertices outside the $\gamma$-complete subgraph.

joint work with Derek Corneil (Toronto), Marc Tedder (Toronto), Christophe Paul (Montpellier)

We present a general scheme to design linear time recursive algorithm on graphs. As an application I will detail an algorithm that computes the modular decomposition tree of an undirected graph in linear time. This algorithm was presented at Icalp 08 (12 pages) and the full is version (42 pages) is now available at https://arxiv.org/abs/0710.3901

To this aim I will present the combinatorial structures needed. In particular the linear time behavior heavily relies on the recursive structure of a nice graph search : Lexicographic Breadth First Search (LexBFS).

Recent developments in the intersection of structural graph theory, parameterized algorithms, and finite model theory have provided several unifying results on the existence of efficient algorithms for problems on graphs. These results apply to problems that satisfy some descriptive condition (typically refering to expressibility in some logic), when restricted to classes of inputs with certain structural characteristics. While such results provide a systematic understanding of tractability, it is yet unclear what compromises between descriptive and structural conditions can yield algorithms with optimized running times. In this talk, we present preliminary results in this topic, as well as some research directions towards proving unifying theories for optimal algorithms.

Sparsest cut is a fundamental graph problem, which models a general notion of balanced separator of a graph, and has uses in graph theory and divide-and-conquer approaches. In it, we are given an edge-capacitated graph, together with demands over pairs of vertices, and we want to find a cut that minimizes the ratio between the capacities and demands across the it. In other words, we aim to separate as much demand as possible using little cut capacity. For general graphs, the best known approximation factor is Õ((log n)^0.5), and the problem is known to have no constant-approximation under the unique games conjecture.

In this talk, we focus on the simpler setting of bounded-treewidth graphs, and present new constant-factor approximation algorithms. Known algorithms in this setting are either inefficient or have large approximation factors. We will see that these algorithms can be framed as specific cases of a general algorithm with uses beyond sparsest cut, and then show how to combine the best of both approaches to obtain efficient and good approximations to the problem. As a result, we give the first constant-factor approximation algorithm running in FPT time.

A graph homomorphism is a mapping between the vertex sets of two graphs that preserves adjacency. Graph homomorphisms do generalize graph colorings and related computational problem have been well studied. Deciding whether there is a homomorphism between two graphs is NP-complete in general.

We consider graph homomorphisms from the point of view of reconfiguration: Given two graphs G and H, we study a reconfiguration graph Col(G,H) whose vertices are graph homomorphisms, where two graph homomorphisms are adjacent if they differ on a single vertex. For a fixed graph H, we consider the computation complexity of 1) Deciding if there is a path between two homomorphisms in Col(G,H); and 2) Deciding if Col(G,H) is connected.

We show how topological methods can be used in both settings to obtain polynomial algorithms for 1) and hardness results for 2). 1) is joint work with Moritz Mühlenthaler (G-SCOP, UGA) and Benjamin Lévêque (G-SCOP, CNRS). 2) is joint work with Moritz Mühlenthaler and Mark Siggers (KNU, Korea).