In this talk, I will present some results on the characterization and the recognition of graph classes.

A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy hardly ever leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal.

We study specifically graphs that have an ordering avoiding some ordered structures that we call *patterns*. Several well-known classes such as chordal, bipartite, interval, and comparability graphs have a characterization in terms of forbidden patterns. It is also known that any class defined by a set of forbidden patterns on three nodes can be recognized in polynomial time. In a recent paper, we've characterized systematically all the classes defined by sets of forbidden patterns (on three nodes). Surprisingly there is a relatively small number of them, and they are all well-known. Also, almost all of them can actually be recognized in linear time. I will talk about these results and about the rich structure of the classes defined by patterns. I will also talk about on-going work in building bridges between intersection graphs and patterns on four vertices.

Distributed certification is a sub-topic of distributed computing aiming at providing tools for enabling a set of autonomous computing entities (a.k.a. processes) to coordinate for deciding whether the distributed system at hand satisfies a given correctness certificates. Among many scenarios, one important aspect of this line of study is certifying that the actual network of processes satisfies some given graph properties (e.g., being 3-colorable, being acyclic, being planar, etc.). The main constraint for deciding whether the property holds is that computation must be local, that is, every process may interact only once with its neighbors in the network. Not all graph properties are decidable under this constraint. For those “locally undecidable“ classes, it is however possible to distribute a proof that the network satisfies the property, by assigning small certificates to the nodes, which can then be checked locally. Nevertheless, some properties (e.g., non 3-colorability) may require huge certificates. To decrease the size of the certificates, interactive proofs have been considered, where every process interacts first with an external entity (e.g., the “cloud“) before interacting locally with its neighbors for forging its opinion regarding whether the graph satisfies the property or not. The talk will present these different mechanisms. It will illustrate them using specific graph properties like planarity and bounded genus, and will discuss the ability to certify graph excluding a specific given minor.

In his 1965 seminal paper on edge colouring, Vizing proved that a (Delta+1)-edge colouring can be reached from any given proper edge colouring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? In other words, if the graph is Delta-edge-colourable, can we always reach a Delta-edge-colouring? If true, this would imply a more recent conjecture of Mohar (2006) that in any graph, all (Delta+2)-edge-colourings are equivalent up to a series of Kempe changes. We discuss recent progress around these questions.

A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in 1998. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. It is true if $G=\Theta_{2,2,2,2}$, which was proved by Voigt and Tuza in 1996. However, this conjecture was disproved by Meng, Puleo, and Zhu in 2017. They showed that if $G=\Theta_{r,s,t}$ where $r,s,t$ have the same parity and $\min\{r,s,t\} \ge 3$, or $G=\Theta_{2,2,2,2p}$ with $p \ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo, and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which –automatically– converts a tree decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.

Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs and planar graphs, to name a few. We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many such classes – where the distance VC-dimension of a graph G is defined as the VC-dimension of its ball hypergraph: whose hyperedges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free graphs has distance VC-dimension at most |V(H)|− 1.

• Our first main result is a Monte Carlo algorithm that on graphs of distance VC-dimension at most d, for any fixed k, either computes the diameter or concludes that it is larger than k in time O(k · mn^{1−εd}), where εd ∈ (0; 1) only depends on d. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such graphs. • Then as a byproduct of our approach, we get a truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense graph classes. The latter classes include all proper minor-closed graph classes, bounded-degree graphs and graphs of bounded expansion. • Finally, we show how to remove the dependency on k for any graph class that excludes a fixed graph H as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such graphs one obtains a truly subquadratictime randomized algorithm for computing their diameter.

We note that all our results also hold for radius computation. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of ε-nets, region decomposition and other partition techniques.

If time allows, I will also mention recent improvements of the above results, to eccentricity and distance oracle computations.

This is joint work with Michel Habib and Laurent Viennot.

The closeness centrality measure associates to each node of a graph its average distance from all the other nodes. In this talk, we will consider a temporal version of this measure, which have been recently introduced and analysed in the case of temporal graphs (that is, graphs in which edges can appear and disappear during time). In particular, we will show how this measure can be efficiently approximated by using a “backward” temporal breadth-first search algorithm and a classical sampling technique. We will then introduce a “temporally global” closeness centrality measure of a node in a temporal graph, which is quite similar to the notion of AUC (Area Under Curve), and we will show how this global measure can also be efficiently approximated. We conclude by presenting several experimental results in the case of medium/large real-world temporal networks. This is a joint work with Clémence Magnien and Andrea Marino.

In this talk, I introduce some results obtained during my Ph.D. All of them deal with cut and connectivity problems in graphs. I present the parameterized complexity of the Partial One-Target Cut (POTC) problem, where the objective is to identify the smallest edge cutset separating a certain proportion r of sources into an input set S={s_1,…,s_k} with a single target t. I provide the proof that POTC is fixed-parameter tractable (FPT) parameterized by the cutset size p. This means that an algorithm finds an exact solution in time f(p)P(n), where f is an arbitrary function, P a polynomial function, and n the instance size. The algorithm is based on the random sampling of important separators. This result highlights a surprising complexity gap between the edge and the vertex versions of the problem. Indeed, when the cutset is made up of vertices, POTC is unlikely to be FPT.

A temporal graph with lifetime $T$ is a pair $(G,\lambda)$ where $G$ is a simple graph with $n$ nodes and $\lambda:E(G)\rightarrow [T]$ is a function of discrete-timed labels telling the snapshots where an edge is active. As recently defined, a temporal coloring of $(G,\lambda)$ is a coloring of each snapshot that properly colors each edge at least once throughout its lifetime; and the \emph{temporal chromatic number of $(G,\lambda)$} is the minimum number $t\chi(G,\lambda)$ of colors that can be used to get a temporal coloring.

In this talk, I will present the results, obtained in collaboration with Andrea Marino, in which we focus on temporal graphs whose edges remain active for at least $t$ timestamps (these are called $t$-persistent temporal graphs). Among other things, we: 1) give some upper bounds for the minimum number of colors needed in terms of $t$ and of the chromatic number of the underlying static graph $G$; 2) prove that $k$ colors are always sufficient when $t$ is at least $\log_k n$, and that if $t$ is smaller, then it is NP-complete to decide whether $k$ colors are enough; 3) prove that the problem is NP-complete even when $G$ has bounded treewidth, and each snapshot is planar and has constant size; and 4) give an FPT algorithm with parameters the treewidth of $G$ and $T$.

Our results also imply many interesting facts: for instance, we know that if $G$ is planar and 2-persistent, then 2 colors are always sufficient