We consider the number of paths that must pass through a subset X of vertices of a capacitated network N in a maximum sequence of arc-disjoint paths connecting two vertices y and z. We consider then the difference between the maximum flow value from y to z in N and the maximum flow value from y to z in the network obtained by N by setting to zero the capacities of arcs incident to X. When X is a singleton, those quantities are involved in defining and computing the flow betweenness centrality and are commonly identified without any rigorous proof justifying the identification. On the basis of a deep analysis of the interplay between paths and flows, we prove that, when X is a singleton, those quantities coincide. On the other hand, we prove that, when X has at least two elements, those quantities may be different from each other. By means of the considered quantities, two conceptually different group centrality measures, based on paths and flows respectively, can be naturally defined. Such group centrality measures both extend the flow betweenness centrality to groups of vertices and are proved to satisfy a desirable form of monotonicity.

Presentations given by students who will be presenting at JGA 2024.

Hector Buffière: Shallow vertex minors, stability, and dependence (abstract: https://jga2024.sciencesconf.org/579556)

Renaud Torfs: Biclique maximum des graphes Star_1,2,3-free sans jumeau et des graphes de bimodularwidth bornée (abstract: https://jga2024.sciencesconf.org/579711)

Guillaume Aubian: Une construction de graphes de grand nombre chromatique sans triangle (abstract: https://jga2024.sciencesconf.org/581565)

Jules Bouton Popper: Comment rendre un graphe temporel connecté ? (abstract: https://jga2024.sciencesconf.org/581190)

Presentations given by students who will be presenting at JGA 2024.

Cyril Pujol: Extremal sizes of cores of products of graphs (abstract: https://jga2024.sciencesconf.org/578775)

Etienne Objois: Constructing tree-based linear oblivious routings (abstract: https://jga2024.sciencesconf.org/581340)

Hugo Demaret: Nombre domatique fractionnaire et degre minimum (abstract: https://jga2024.sciencesconf.org/576944)

Positional games are a family of two-player games which includes tic-tac-toe, Hex and Sim for example. The board is a hypergraph i.e. a set of vertices along with a set of (hyper)edges which are subsets of vertices. Alice and Bob take turns claiming vertices one by one, with goals that depend on the chosen convention of play. This talk focuses on recent results on the “Maker-Breaker” convention: Alice (“Maker”) aims at claiming all the vertices of some edge, whereas Bob (“Breaker”) aims at preventing her from doing so. Since no draw is possible, there are only two possible outcomes for any given hypergraph: either Maker has a winning strategy, or Breaker has a winning strategy. Deciding the outcome is PSPACE-complete [Schaefer, 1978] even for hypergraphs with all edges of size 6 [Rahman & Watson, 2021]. We establish tractability for hypergraphs with all edges of size at most 3. We also present some complexity results about a new version of the game, where a poset is added on the vertex set to restrict the players' moves, in the fashion of Connect-4.

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).