|
June 5th 2026, Campus de Jussieu, Bâtiment Esclangon, Amphitéâtre Herpin.
|
Join work with Quentin Japhet, Marc-Antoine Weisser et Dominique Barth A line-digraph is a variant of the definition of linegraphs for directed graphs. Given a directed graph $G = (V, A)$, the line-digraph H of G has one vertex for each edge in A, and a vertex u in H is connected to another vertex v if the arcs associated with u and v in G form a path of length 2. As with linegraphs, line-digraphs can be characterized by forbidden subgraphs, referred to hereafter as patterns. In this presentation, we consider the problem of calculating the edit distance from a directed graph to a line-digraph with the same vertices. We are allowed to add or remove arcs from a directed graph to transform it into a line-digraph. The edit distance is the minimum number of operations required to achieve this. We will examine, through the computational complexity and parameterized complexity, which patterns seem to make the problem difficult; in particular, we will show that the complexity of the problem can vary depending on the presence or absence of some of the patterns in the input graph.
A graph G is prismatic if for every triangle T of G, every vertex of G that is not in T, has exactly one neighbor in T. The complement of a prismatic graph is called antiprismatic. The complexity of the coloring problem when restricted to prismatic graphs is unknown. Hence, the complexity of the clique-covering problem on prismatic graphs is also unknown. Chudnovsky and Seymour gave a full structural description of prismatic graphs. They divided the class in two subclasses : the orientable prismatic graphs and the non-orientable prismatic graphs. Preissman, Robin and Trotignon gave an algorithm to solve the clique problem in non-orientable prismatic graphs in polynomial time. We show this algorithm can also be used for prismatic graphs with no 2K_1 + C_4 (co-bridge), whether they are orientable or not. To achieve this, we show that this class of graphs admits a bounded number of disjoint triangles through a cautious analysis of their structure. This is a joint work with Eileen Robinson (Université libre de Bruxelles).
The main result we will discuss in this talk is some new evidence that standard dynamic programming algorithms parameterized by treewidth (including for k-Coloring, Independent Set, and Max Cut) are likely to be best-possible. In particular, we will explain why an improvement on such algorithms would violate not only the Strong Exponential Time Hypothesis (SETH), but would also imply faster-than-expected algorithms for the k-SUM problem. Along the way, we will discuss the connections between cool but seemingly unrelated topics such as graph width measures, interactive proof protocols, and perfect hashing schemes.
The state of art of linear-time recognition for some graphes classes is using LexBFS, in two or three passes, for Trivially Perfect Graphs and Unit Interval Graphs, respectively. However, we show that one or two passes of a simple breadth-first or depth-first search, using a static degree condition, and thus the usual implementation of such searches, does the job. The pattern characterization of vertex orderings is the key to prove the result.
In this talk we survey existing results, techniques and open problems for Colouring and k-Colouring on special graph classes. A graph G is H-subgraph-free if G does not contain H as a subgraph, and G is H-free if G does not contain H as an induced subgraph. Moreover, G is probe H-free if it can be made H-free by adding edges within some independent set of G. In particular, we consider H-free graphs, probe H-free graphs and H-subgraph-free graphs, and discuss how structural properties of these graph classes can be exploited to obtain efficient algorithms for Colouring and k-Colouring.