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

the dichromatic number of a digraph is the minimum integer k such that the set of vertices of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is the same as the dichromatic of the digraph obtained from G by replacing each edge by a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerned with chromatic number of undirected graphs have been generalised to digraphs via the dichromatic number. However, no concept of clique number for digraphs was available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and chromatic number in undirected graphs. We will focus on studying the notion of chi-boundedness in particular. This is a joint work with Guillaume Aubian, Pierre Charbit and Raul Lopes.

The connection between excluding complete graphs (for different notions of exclusion) and the chromatic number of graphs is about a century old. In the 1940s, Hadwiger conjectured that a graph with no Kn minor is (n-1)-colorable. Later, in the 1950s, Hajós made a strengthening this conjecture, that every graph that contains no subdivision of Kn as a subgraph, is (n-1)-colorable. While both conjectures still have open cases, the existence of a bound c=c(n) instead of n-1 for the chromatic number is known for both conjectures. An attempt to strengthen this result would be to ask whether there exists a constant c=c(n) such that every graph with no subdivision of Kn as an induced subgraph is c-colorable. This question is a special case of Scott's conjecture from the 1990s. The only known cases of Scott's conjecture for complete graphs Kn was for n at most 4, where a constant bound exists (a result by Lévêque, Maffray, and Trotignon). With Nicolas Trotignon, we proved that no such bound exists for n at least 5. In this talk, I present the techniques used to prove this result as well as some other applications of the technique in chi-boundedness. This result is from arXiv:2112.11970.

Temporal graphs model time-varying relationships in dynamic systems. Key problems include paths and connectivity. In static graphs Menger's Theorem states the maximum number of internally disjoint paths between non-adjacent vertices equals the minimum vertices needed to cut all paths. This combined with flow techniques also leads to polynomial time algorithms to compute disjoint paths and cuts. A natural question is therefore whether such results carry over to temporal graphs, where the paths/walks between a pair of vertices must respect the flow of time. The first obstacle in such question is the definition of robustness in this context, i.e., how are the paths/walks to be disjoint. We discuss three possible types of robustness, each of which leading to the definition of two optimization parameters, one concerning the maximum number of disjoint paths, and the other the minimum size of a cut.

In graph theory, a dynamic network can be understood as a global underlying graph whose edges are allowed to become temporarily unavailable at times. Extending Courcelle-like meta theorems to such a temporal setting is an important and challenging open question.

Without the consideration of temporality, a good number of width parameters has been introduced in the effort to better understand what lies between cliquewidth (number of different neighbourhoods) and treewidth (total size of neighbourhoods). We can cite rankwidth, bimodule-width, booleanwidth, and matching-width for the first category; and minor-based parameters such as Hajos/Hadwiger number and twinwidth for the second one. However, attempts in extending those parameters to temporal graphs are still scarce in the literature.

Twins in a temporal context would refer to vertices which are substitutes for each other in the solution of a number of classical graph problems, e.g. matching, epidemic spreading, journeys of optimal (temporal) length, and so on. Although most of these problems become NP-hard to optimise on an arbitrary input, we present in this talk an example where reducing a spatiotemporal input into a timeless graph and using both geometric and decomposition properties help in obtaining a PTAS solution. We hope this kind of technique could help in solving problems beyond first order logic when exploiting the conformist nature of twins.

We extend known properties of chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called alpha_i-metric (i in N) if it satisfies the following alpha_i-metric property for every vertices u,w,v and x: if a shortest path between u and w and a shortest path between x and v share the terminal edge vw, then d(u,x) >= d(u,v) + d(v,x)-i. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a ,,near-shortest'' path with defect at most i. It is known that alpha_0-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are alpha_i-metric for i=1 and i=2, respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an alpha_i-metric graph can be computed in total linear time. Our strongest results are obtained for alpha_1-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called (alpha_1,Delta)-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers to a question raised in (Dragan, IPL, 2020). Our algorithms follow from new results on centers and metric intervals of alpha_i-metric graphs. In particular, we prove that the diameter of the center is at most 3i+2 (at most 3, if i=1). The latter partly answers to a question raised in (Yushmanov & Chepoi, Mathematical Problems in Cybernetics, 1991).

The graph planarity testing problem asks whether we can draw an input graph in the plane in such a way that it is actually crossing-free (or embedded). In a seminal paper from 1974, Hopcroft and Tarjan gave a linear-time algorithm for this problem, initiating a long series of variations and generalizations. One of them is to make the target space more general, namely, to consider embeddings not into the plane, but into a more general surface. It is known that the problem of deciding the embeddability of a graph into a surface is NP-hard, but Mohar (1999) and Kawarabayashi, Mohar, and Reed (2008) gave algorithms that are linear in the size of the graph (and exponential in the genus of the surface).

In this talk, we consider an even more general case, in which the target space is a 2-dimensional simplicial complex (a topological space obtained from a graph by attaching a solid triangle to some of its 3-cycles). It turns out that this generalization encompasses some other well known problems, such as the crossing number problem and the planarity number problem (and their generalizations to surfaces). We give an algorithm that is quadratic in the size of the input graph (and exponential in the size of the input complex), independent from the previous algorithms to embed graphs into surfaces. The techniques mix graph theory (branchwidth, excluded grid theorem, dynamic programming) with topology (combinatorial maps of graphs on surfaces).

This is joint work with Thomas Magnard.

A proper vertex coloring of a graph is said to be odd if for each non-isolated vertex there is a color appearing an odd number of times among its neighbors. It is said to be conflict-free if for each non-isolated vertex there is a color appearing exactly once among its neighbors. In [Caro et al., Remarks on proper conflict-free coloring of graphs, Discrete Mathematics 346 (2023) 113221] it was proved that any claw-free graph with maximum degree k has a conflict-free coloring with at most 2k +1 colors. In this talk we show that this upper bound can be improved to k + 6, and to k + 4, for quasi-line graphs, a proper subclass of claw-free graphs. Our result relies on a recoloring technique which could be useful to derive similar results for other families of graphs and for odd colorings as well. Joint work with: Martin Matamala (Universidad de Chile).

Generalised Mycielskians of odd cycles are relatively small graphs with high odd girth and chromatic number 4. In the literature there are many proofs using different techniques, like methods from algebraic topology, to show the second property. It is also proven by DeVos et al that these graphs have circular chromatic number 4. Using a result from about the same time of Simonyi and Tardos, namely that for a “topologically t-chromatic” graph $G$, where $t$ is even we have $\chi_c(G) = \chi(G) = t$, one can also get this strengthened statement.

In this talk we present a new, relatively short direct proof for the circular chromatic number, using only a basic notion of algebraic topology, namely the winding number. Then we present another graph family with high odd girth and circular chromatic number 4. This construction is very similar to the generalized Mycielski, but on its first two layers it forms a M$\ddot{o}$bius ladder. We prove the statement about their circular chromatic number with similar techniques. Moreover we present a similar result for a family of signed graphs.

This talk is based on a joint work with Reza Naserasr (Universit´e de Paris, IRIF, CNRS, F-75006, Paris, France), S Rohini (Indian Institute of Technology Madras, India) and S Taruni (Indian Institute of Technology Dharwad, India).

A first objective of this talk is to show that complements of line graphs enjoy nice coloring properties. For instance, all complements of line graphs have their local chromatic number equal to their (usual) chromatic number. There is also an elementary sufficient condition for their chromatic number to be equal to a natural upper bound, with various consequences such as a complete characterization of all induced subgraphs of the Kneser graph KG(n, 2) that have a chromatic number equal to its chromatic number, namely n − 2. A second objective is to take this topic as an opportunity to discuss the limits of the topological method. This latter is especially suitable for the study of coloring properties of complements of line graphs. Nevertheless, there are clues showing that most of our results cannot be obtained by the topological method. Joint work with Hamid Reza Daneshpajouh and Guilhem Mizrahi.

Is it always beneficial to create a new relationship (have a new follower/friend) in a social network? This question can be formally stated as a property of the centrality measure that defines the importance of the actors of the network. Score monotonicity means that adding an arc increases the centrality score of the target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the arc relatively to the remaining nodes. It is known that most centralities are both score and rank monotone on directed, strongly connected graphs. In this paper, we study the problem of score and rank monotonicity for classical centrality measures in the case of undirected networks: in this case, we require that score, or relative importance, improve at both endpoints of the new edge. We show that, surprisingly, the situation in the undirected case is very different, and in particular that closeness, harmonic centrality, betweenness, eigenvector centrality, Seeley's index, Katz's index, and PageRank are not rank monotone; betweenness and PageRank are not even score monotone. In other words, while it is always a good thing to get a new follower, it is not always beneficial to get a new friend.

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. We extended the Theorem of Hoàng by proving the following : Let G be a graph with degree sequence d_1,d_2,…,d_n and let t be a positive integer at most 4. If G is t-tough and if. ∀ i, t ≤ i <n/2, d_i ≤ i ⇒ d_{n−i+t} ≥ n−i then G is Hamiltonian. To do this, we extend the closure lemma due to Bondy and Chvàtal. This is joint work with Chình T. Hoàng

Since the seminal work of Vapnik and Chervonenkis (1971), one of the basic quantities describing the complexity of a set system is the VC-dimension. As such, VC-dimension is the foundation of many theoretical results in learning theory, in computational geometry, and recently, in graph theory.

While for simple geometric set systems (e.g. ones induced by half-spaces), one can bound the VC-dimension using elementary arguments, many applications require more complex set systems. A long standing central open problem since 1989 was bounding the VC-dimension of unions and intersections of half-spaces in high dimensions. In collaboration with A. Kupavskii and N. Mustafa, we resolved this problem by providing a tight lower bound in dimensions at least 4.

In this talk, I give an introduction to the notion of VC-dimension, present our bounds on the VC-dimension of unions and intersections of half-spaces, then discuss some results on graphs with bounded VC-dimension.

No prior knowledge of computational geometry or learning theory is required.

A part of the talk is based on the paper M. Csikós, A. Kupavskii, N. H. Mustafa — Tight Lower Bounds on the VC-dimension of Geometric Set Systems (Journal of Machine Learning Research, 2019)

The $B$-polynomial defined by J. Awan and O. Bernardi is a generalization of Tutte Polynomial to digraphs. In this paper, we solve an open question raised by J. Awan and O. Bernardi regarding the expansion of $B$-polynomial in elementary symmetric polynomials. We show that the quasisymmetric generalization of the $B$-polynomial distinguishes a certain class of oriented proper caterpillars, and the class of oriented paths. We present a recurrence relation for the quasisymmetric $B$-polynomial involving deletion of a source or a sink. As a consequence, we prove that a class of digraph $\mathcal{D}$ is distinguishable if and only if the class $\mathcal{D}^{\vee}$ obtained by taking directed join of $K_1$ with each digraph in $\mathcal{D}$ is distinguishable, which concludes that the digraph analogue of Stanley's Tree conjecture holds for a large class of acyclic digraphs.

A convex polytope $P \subset \R^d$, i.e. the convex hull of finitely many points in $\R^d$, can always be described by finitely many affine (in)equalities. The minimal number of inequalities needed for a description via affine constraints, is the number of facets of the polytope, we call it the size of the polytope. If $Q \subset \R^{d+r}$ is a polytope, and $\pi : \R^{d+r} \to \R^d$ an affine map such that $\pi(Q)=P$, one says that $Q$ is a (linear) lift of $P$. Some combinatorial polytopes $P_n$ admit a \emph{compact formulation}, meaning there exists a lift $Q_n$ of $P_n$, whose size is poly$(n)$. The search for compact formulation(s) is motivated by (linear) optimization problems. In this talk, we will introduce the spanning tree polytope $P_{SpT}(G)$ of a graph $G$, and present a compact formulation of $P_{SpT}(G)$, whose size is less than $n^3$ (where $n$ denotes the number of vertices of $G$). We will further discuss the case when $G=K_n$ is the complete graph on $n$ vertices, and the case of planar graphs.

The problem of reconfiguring independent sets belongs to the broader field of combinatorial reconfiguration problems. It can be formulated as follows: given a collection of tokens placed on the vertices of an independent set of a graph, is it possible to move one by one these tokens to another target independent set, such that two tokens are never neighbors throughout the transformation? After a general introduction to combinatorial reconfiguration and the independent set reconfiguration problem, we will focus on the “Token Sliding” variant. In this variant, one step of the transformation consists in moving a token from a vertex to a neighboring vertex. We will focus on the parameterized complexity of this problem in sparse classes of graphs and on the new tools we have recently designed for the development of FPT algorithms.

In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem has mainly been studied on undirected graphs, and has gained a lot of attention in recent years, mainly because of its difficulty: it is NP-complete and has a best polynomial-time approximation factor of log(n) even on very restricted graph classes. We focus our study on directed and oriented graphs (the difference is that directed graphs may contain 2-cycles, unlike oriented graphs), for which the Metric Dimension has been recently studied. We prove that Metric Dimension remains NP-hard, even on planar DAGs of maximum degree 6. However, we find linear-time algorithms solving the problem on directed trees (directed graphs whose underlying graph is a tree) and on orientations of unicyclic graphs. Finally, we give a fixed-parameter-tractable algorithm for directed graphs when parameterized by modular-width.

Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games have been studied since the introduction of the game of SIM in 1968, but only few complexity results have been found out about them. In 2001, Slany proved some partial results on Avoider-Avoider games complexity, and in 2017 Bonnet et al. proved that short Avoider-Enforcer games are Co-W[1]-hard. More recently, in 2022, Miltzow and Stojaković proved that these games are NP-hard. As these games correspond to the misère version of the well-known Maker-Breaker games, introduced in 1963 and proven PSPACE-complete in 1978, one could expect these games to be PSPACE-complete too, but the question has remained open since then. During this talk, we will show that both Avoider-Avoider and Avoider-Enforcer conventions are PSPACE-complete, and that consequently, some particular Avoider-Enforcer games also are.

It is a common strategy to solve efficiently NP-complete problems on graphs by exploiting one of its adventageous structural parameters. This approach has led to the very potent theory of parameterized complexity, in which some parameters such as treewidth or cliquewidth have emerged as especially efficient to design fast parameterized algorithms.

Following the same principle, Bonnet et al. have very recently introduced the notion of contraction sequence of a graph: the high-level idea is to gain time by treating similarily vertices with a similar neighborhood, generalizing naturally the algorithms on cographs.

The quality of a contraction sequence can be mesured by two (among other) non-functionally equivalent parameters called twin-width and component twin-width. It is clear that the primary focus of Bonnet et al. was twin-width, leaving component twin-width almost unexplored in the whole literature.

It is known that cliquewidth and component twinwidth are functionnaly equivalent: Bonnet et al. proved this result through functional equivalence with booleanwidth (which is known to be functionnaly equivalent with cliquewidth), which leads to an exponential bound on component twin-width by cliquewidth; and a double-exponential bound on cliquewidth by component twin-width.

In this presentation, I will prove that these two bounds can be drastically improved: we will obtain very simple linear bounds. Then, I will give an example of a concrete application of component twin-width (using dynamic programming) that always beats the best known upper bounds of the complexity of a counting version of several graph coloring problems. Finally, I will discuss how the linear bounds obtained can be used to extend the results known on the approximations of cliquewidth to approximations of component twinwidth.

A proper k-vertex coloring of a digraph D is a mapping $c:V(D) \rightarrow \{1,\cdots,k}$ such that no two adjacent vertices are assigned the same color. In this case we say that D is k-colorable. The minimum k for which a digraph D is k-colorable is called the chromatic number of D. How does the chromatic number of a digraph relate to other digraph's invariants, such as connectivity, girth and subdigraphs?

During this talk we are going to present how the existence of certain types of paths and cycles in a digraph affects its chromatic number.

Each hereditary property can be characterized by its set of minimal obstructions; these sets are often unknown, or known but infinite. By allowing extra structure it is sometimes possible to describe such properties by a finite set of forbidden objects. This has been studied most intensely when the extra structure is a linear ordering of the vertex set. For instance, it is known that a graph G is $k$-colourable if and only if $V(G)$ admits a linear ordering $\le$ with no vertices $v_1 \le \cdots \le v_{k+1}$ such that $v_iv_{i+1} \in E(G)$ for every $i \in \{ 1, \dots, k \}$. In this talk, we have a look at such characterizations when the extra structure is a circular ordering of the vertex set. In particular, we show that the classes that can be described by finitely many forbidden circularly ordered graphs include forests, circular-arc graphs, and graphs with circular chromatic number (strictly) less than $k$.

Nowhere-zero flows of unsigned graphs were introduced by Tutte in 1954 as a dual problem to vertex-coloring of (unsigned) planar graphs. The definition of nowhere-zero flows on signed graphs naturally comes from the study of embeddings of graphs in non-orientable surfaces, where nowhere-zero flows emerge as the dual notion to local tensions. Nowhere-zero flows in signed graphs were introduced by Edmonds and Johnson in 1970 for expressing algorithms on matchings, but systematically studied first by Bouchet in 1983. Bouchet also stated a conjecture which occupies a central place in the area of signed graphs: Every flow-admissible signed graph admits a nowhere-zero 6-flow. There is a significant difference in the flows of signed graphs and unsigned graphs. In this talk I will talk about the progress on the development of the flow theory of signed graphs.

Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for a positive integer $k$, we seek a vertex ordering such every vertex can (weakly respectively strongly) reach in $k$ steps only few vertices that precede it in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in the structural and algorithmic graph theory. Recently, Dvo\v{r}\'ak, McCarty, and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in $\mathbb{R}^d$, such as homothets of a compact convex object, or comparable axis-aligned boxes.

In this paper, we prove upper and lower bounds for the $k$-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in $k$, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).

This is joint work with Zden\v{e}k Dvo\v{r}\'{a}k, Jakub Pek\'arek and Torsten Ueckerdt.

The lottery ticket hypothesis states that a randomly-initialized neural network contains a small subnetwork which, when trained in isolation, can compete with the performance of the original network. Recent theoretical works proved an even stronger version: every sufficiently overparameterized (dense) neural network contains a subnetwork that, even without training, achieves accuracy comparable to that of the trained large network.These works left as an open problem to extend the result to convolutional neural networks (CNNs). In this work we provide such generalization by showing that, with high probability, it is possible to approximate any CNN by pruning a random CNN whose size is larger by a logarithmic factor.

We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that it is carried out exclusively through the spiking of neurons. Even though much has been accomplished in the blocks world over the past five decades, we believe that this is the first algorithm of its kind. The input is a sequence of symbols encoding an initial set of block stacks as well as a target set, and the output is a sequence of motion commands such as “put the top block in stack 1 on the table”. The program is written in the Assembly Calculus, a recently proposed computational framework meant to model computation in the brain by bridging the gap between neural activity and cognitive function. Its elementary objects are assemblies of neurons (stable sets of neurons whose simultaneous firing signifies that the subject is thinking of an object, concept, word, etc.), its commands include project and merge, and its execution model is based on widely accepted tenets of neuroscience. A program in this framework essentially sets up a dynamical system of neurons and synapses that eventually, with high probability, accomplishes the task. The purpose of this work is to establish empirically that reasonably large programs in the Assembly Calculus can execute correctly and reliably; and that rather realistic – if idealized – higher cognitive functions, such as planning in the blocks world, can be implemented successfully by such programs. This is a joint work with Francesco d'Amore, Daniel Mitropolsky, Emanuele Natale, and Christos H. Papadimitriou.

Given n points in the Euclidean plane, they are either all collinear or define at least n distinct lines. This result is a corollary of the Sylvester-Gallai theorem. Its combinatorial generalization was proven by de Bruijn and Erdös in the forties. In 2008, Chen and Chvátal described a generalization of the notion of a line to any metric space and conjectured that the same result remains true in that framework. Since then, a growing community of researchers has been investigating this question. It remains open for metric spaces and even for those specific metric spaces generated by graphs. In this talk, we shall see a broad overview of the state of research on the matter: results and (many!) remaining open questions.

Let $\mathcal{S}$ be a family of (not necessarily axis parallel) squares in the plane. The \emph{transversal number} of $\mathcal{S}$, denoted by $\tau(\mathcal{S})$, is the minimum number of points needed to hit all the squares in $\mathcal{S}$, and the \emph{independence number} of $\mathcal{S}$, denoted by $\nu(\mathcal{S})$, is the maximum number of pairwise disjoint squares in $\mathcal{S}$.

Clearly, $\tau(\mathcal{S})$ is at least $\nu(\mathcal{S})$. We prove that $\tau(\mathcal{S}) \leq 10 \nu(\mathcal{S})$ and present a family where $\tau(\mathcal{S}) = 3\nu(\mathcal{S})$.

During the talk, we will sketch the proof of the main result and remark how to extend our approach to families of rectangles with \emph{bounded aspect ratios}.

This is joint work with András Sebő.

The art gallery problem is to determine the number of guards (or surveillance cameras) sufficient to cover or see every point in the interior of an art gallery. An art gallery can be viewed as a polygon P (with or without holes) with a total of n vertices, and guards as points in P. Any point z in P is said to be visible from a guard g if the line segment joining z and g does not intersect the exterior of P. This problem was first posed by Victor Klee in a conference in 1973, and in the course of time, it has become an important problem in computational geometry with extensive applications to surveillance of buildings like airport terminals, railway stations etc. A polygon is said to be guarded by a set of chosen guards if every interior point of P is visible from some guard within the guard set.

Chromatic art gallery problems arise from applications in areas like landmark-based robot navigation and wireless networks. One such problem is the weak-conflict free guarding of polygons, where the objective is to colour a chosen guard set S for P using the minimum number of colours such that each point within P sees at least one guard from S with a unique colour. Note that the objective here is to minimize the number of colors rather than the number of guards in S. We present an algorithm for weak conflict-free guarding of P (without holes) where the point guard set is coloured using only O(log n) colours. If the guards are allowed to place only on vertices of P, the corresponding algorithm for weak conflict-free vertex guarding problem uses O(log^2 n) colours. This algorithm uses funnel structures of weak visibility polygons for placing coloured guards.

Finally, we discuss a few open problems on weak conflict-free guarding of P for both point and vertex guards.

A signed graph $(G, \sigma)$ is a graph $G$ along with a function $\sigma: E(G)\to\{+,-\}$. A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The chromatic number (this is one of the many notions of chromatic number for signed graphs available in literature) of a signed graph $(G, \sigma)$ is the minimum number of vertices $|V(H)|$ of a signed graph $(H, \pi)$ to which $(G, \sigma)$ admits a homomorphism.

Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the chromatic number. In this work, we provide new results and bounds on the chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs).

Joint work with: Bensmail, Das, Nandi, Pierron, Sopena

We survey several different methods of constructing infinite graphs out of the families of finite graphs, among the Fraîssé limits, the morasses, the ultraproducts and the graphons/measurings. Concentrating on a couple of them, we talk about various colourings and the generalised Ramsey theory.

A segment intersection representation of a graph is a set of segments such that each vertex corresponds to a segment, and such that two segments intersect if and only if the corresponding vertices are adjacent. There exists several proofs that bipartite planar graphs admit segment intersection representation, whose segments are either horizontal or vertical. Furthermore, the representation is such that parallel segments correspond to an independent set.

In his PhD Thesis E.R. Scheinerman conjectured that every planar graph has a segment intersection representation, and he also conjectured that in the case of 3-colorable planar graphs, such a representation exists where only 3 slopes appear, one for each color class. We proved both of these conjectures, and we also proved that such a representation with 4 slopes, one per color class, does not always exist. This last proof relies on the fact that planar signed graphs are not always four colorable, for some signed version of colorings. During the talk we will provide the general idea of these proofs.

These works were joint works with J. Chalopin, L. Isenmann, and C. Pennarun

In the “isomorphism game”, two separated but collaborating players attempt to convince a referee that a given pair of graphs are isomorphic. Any perfect classical strategy for this game corresponds to an isomorphism of the graphs. Thus two graphs are said to be “quantum isomorphic” if the players can win the corresponding isomorphism game using a quantum strategy, i.e., one in which the players can make local measurements on a shared quantum state. Surprisingly, two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. This can be viewed as a quantum analog of a classical theorem of Lovasz stating that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph. A notable aspect of this characterization of quantum isomorphism is that its proof relies heavily on tools from quantum group theory, and thus it provides a link between this field and those of quantum information and combinatorics. Additionally, this characterization can be used to show that the Four Color Theorem is equivalent to every planar graph having a homomorphism to a particular graph on 24 vertices. It remains to be seen whether this last result is actually interesting.

This is joint work with Laura Mančinska.

Given a vector $\vec{x}$ in the null space of the adjacency matrix of a graph $G$, the support of $\vec{x}$ are the vertices which correspond to non-zero coordinates of $\vec{x}$. The support of $G$, $\Supp{G}$, is the union of the supports of all vectors in the null space of its adjacency matrix. The null decomposition of $G$, first introduced by Jaume and Molina in 2018, studies two subgraphs of $G$, $C_S(G)$, induced by the vertices in $\Supp{G}$ and their neighbours, and $C_N(G)$, induced by the remaining vertices.

In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time.

This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur.

In 1980, Edelman defined a poset on objects called noncrossing 2-partitions, made of a partition and a noncrossing partition, with a bijection linking parts of the same size in both partitions. Studying this poset, he proved that the number of noncrossing 2-partitions is given by (n+1)^{n-1}. This is also the number of classical combinatorial objects called parking functions. After introducing noncrossing partitions, noncrossing 2-partitions and parking functions, we will draw the link between parking functions and noncrossing 2-partitions, describing Edelman's poset in terms of parking functions. Afterwards, we will (recall and) use the notion of species introduced in the early 1980s by Joyal to describe the action of the symmetric group on a poset on parking trees.

This is a joint work with Matthieu Josuat-Vergès and Lucas Randazzo.

A natural variant of proper vertex colorings, consists in considering colorings which require different colours for vertices at distance (exactly) p, for some fixed p. For that type of colouring, the answer to the question “how many colours suffice?”, can depend greatly on the parity of p. In the talk I will give an overview of the results on this type of colouring, focusing particularly in the case of planar graphs.

Given a vector $\vec{x}$ in the null space of the adjacency matrix of a graph $G$, the support of $\vec{x}$ are the vertices which correspond to non-zero coordinates of $\vec{x}$. The support of $G$, $\Supp{G}$, is the union of the supports of all vectors in the null space of its adjacency matrix. The null decomposition of $G$, first introduced by Jaume and Molina in 2018, studies two subgraphs of $G$, $C_S(G)$, induced by the vertices in $\Supp{G}$ and their neighbours, and $C_N(G)$, induced by the remaining vertices.

In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time.

This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur.

A weighted point-availability time-dependent network is a list of temporal edges, where each temporal edge has an appearing time value, a travel time value, and a cost value. We consider the single source Pareto problem in weighted point-availability time-dependent networks, which consists of computing, for any destination $d$, all Pareto optimal pairs $(t,c)$, where $t$ and $c$ are the arrival time and the cost of a path from $s$ to $d$, respectively (a pair $(t,c)$ is Pareto optimal if there is no path with arrival time smaller than $t$ and cost no worse than $c$ or arrival time no greater than $t$ and better cost). We design and analyse a general algorithm for solving this problem, whose time complexity is $O(M\log P)$, where $M$ is the number of temporal edges and $P$ is the maximum number of Pareto optimal pairs for each node of the network. This complexity significantly improves the time complexity of the previously known solution. Our algorithm can be used to solve several different minimum cost path problems in weighted point-availability time-dependent networks with a vast variety of cost definitions, and it can be easily modified in order to deal with the single destination Pareto problem.

A self-stabilizing distributed system, regardless its initial configuration, converges within finite time to a configuration from which its behavior is correct. By essence, self-stabilization is a non-masking fault tolerant approach since the arbitrary initial configuration can be seen as the result of arbitrary transient faults.

In this talk, we will consider self-stabilization in highly dynamic networks, i.e., networks suffering from unexpected and frequent topological changes. Precisely, assuming that nodes are uniquely identified, we study the self-stabilizing leader election problem in three important classes of dynamic networks to obtain solutions tolerating both transient faults (such as memory corruption) and frequent topological changes.

We first study conditions under which our problem can be solved and then propose several algorithms. Our results reveal that the assumption on the knowledge of the number N of processes is central. Indeed, we show that, as soon as there is no strong guarantees on the temporal connectivity in the network, the knowledge of the exact value of N is required. Finally, the convergence time of self-stabilizing leader election cannot be bounded in some important cases. In those cases, we show that our solutions are speculative since their convergence time can be still bounded in a subset of more probable executions.

The Kneser graph KG(n,k) is the graph whose vertex set consists of all k-subsets of an n-set, with edges joining pairs of disjoint subsets. Kneser graphs arise naturally in various contexts, and play a central role in fractional colouring. In 1978, Lovasz used tools from algebraic topology to prove that KG(n,k) is (n-2k+2)-chromatic, proving a long-standing conjecture of Kneser and laying the foundations of topological combinatorics. Shortly thereafter, Schrijver defined an induced subgraph SG(n,k) of KG(n,k), known as the Schrijver graph, and showed that SG(n,k) is also (n-2k+2)-chromatic. Moreover, he showed that SG(n,k) is vertex-critical, in the sense that the chromatic number decreases if any vertex is deleted. However, Schrijver graphs are in general not edge-critical: certain edges can be deleted without any effect on the chromatic number. In this talk, I will define an (n-2k+2)-chromatic edge-critical subgraph of SG(n,k), thereby sharpening the classical results of Lovasz and Schrijver.

Joint work with Tomas Kaiser.

A sweep of a point configuration is an ordered partition induced by a linear functional. These orders are at the core of several applications in discrete and computational geometry, and also appear naturally in linear programming. The set of orderings obtained this way is highly structured: isomorphic to the face lattice of a convex polytope. In the plane, they were formalized and abstracted by Goodman and Pollack under the theory of allowable sequences of permutations, but a high dimensional generalization was missing. I will present an overview of the theory, discuss polytopal constructions, and introduce combinatorial generalizations in terms of oriented matroids and allowable graphs of permutations.

This is based on joint work with Eva Philippe.

By extending the notion of indicator to signed graphs, we show the problem of 4-coloring is captured by the problem of C_{-4}-coloring (mapping signed graphs to a negative 4-cycle). Moreover, we extend the notion of H-critical to (H, \pi)-critical. In this talk, we prove that any C_{-4}-critical signed graph on n vertices, except for one particular signed bipartite graph on 7 vertices and 9 edges, must have at least 4n/3 edges. As an application to planarity, we conclude that every signed bipartite planar graph of negative girth at least 8 admits a homomorphism to C_{-4} and show that this bound is the best possible, which is relevant to a bipartite analog of Jaeger-Zhang conjecture.

I will give an overview of the following result. Let k and d be integers. Let G be a graph with maximum average degree at most 2k + 2d/(k+d+1). Then G decomposes into k+1 pseudoforests such that one of the pseudoforests has each connected component containing at most d edges. Here a pseudoforest is a graph where each component contains at most one cycle, and a decomposition is a partition of the edge set into edge disjoint subgraphs. By a result of Fan et al., the bound is best possible for all k and d, even when you ask for one pseudoforest with maximum degree at most d. This is joint work with Logan Grout.

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

We are interested in counting problems which consists in computing the number of solutions to a given instance of the problem. This kind of question has strong connexions, in particular in the case of independent sets, with problems from statistical physics and what is called the hard core distribution. As many counting problems, counting exactly the number of independent sets of a graphs is difficult (i.e., #P-complete) even on bipartite graphs, and even difficult to approximate for general graphs. On the other hands, it was shown to be polynomial time solvable for more restricted classes of graphs such as chordal graphs, cographs or monotone bipartite graphs. We show that the number of independent sets can also be computed in polynomial time for strongly orderable graphs which is a super-class of chordal bipartite and strongly chordal graphs. This is joint work with Haiko Muller.

Packing negative cycles in signed graphs has application to multiflow problem. It allows to predict when the cut condition is sufficient for the existence of a multiflow satisfying the demand. Here the signed edges play the role of the demand, and the unsigned edges play the role of the links. We investigate a min-max relation in this context related to the notion of box totally-dual-integral linear systems.

A strong edge coloring of a graph is an assignment of colors to edges such that every color class induces a matching. The smallest number of colors for which a strong edge coloring of a graph G exists is known as the strong chromatic index and it is denoted by $\chi′_s(G)$. It is already known that the problem of finding the strong chromatic index for arbitrary graphs is NP-complete. In this talk, we will discuss strong edge coloring of unitary Cayley graphs.

A distance labeling consists in coding the distances in a graph by assigning a label L_u to each vertex u, such that the distance between two nodes u and v can be computed from L_u et L_v. We will see that the minimum size of labels in a constant degree graph is related to other parameters coming from combinatorics and communication complexity. The first one is the Ruzsa-Szemeredi number that measures the maximum number of edges in an n-node graph that can be decomposed into n induced matchings (an edge of one matching cannot be incident to two edges of another matching). The second one is the minimum size of messages in the SumIndex problem where Alice knows an n-bit vector X and an index a, Bob knows X and an index b, and where they both send a message to a referee that should compute the bit of X in position a+b mod n from the two messages (the referee does not know X).

Joint work with Adrian Kosowski and Przemyslaw Uznanski.

We revisit the complexity of Coloring with respect to two parameters: the number of given colors k; and the “width” of the input graph w. Here, by width we mean a measure of complexity of the graph. When the notion of width in question is treewidth, the problem is very well-understood: there exists a simple k^w algorithm, and no algorithm can do significantly better under the Strong Exponential Time Hypothesis (SETH), even if we replace treewidth by much more restrictive notions, such distance to linear forest. In this talk we will consider the notion of clique-width, which is the most well-studied generalization of treewidth for dense graphs. We will sketch an algorithm and a matching lower bound (under the SETH) which completely determine the complexity of coloring as a function of clique-width, for any fixed k>=3.

Modular decomposition is a graph decomposition that can be computed in linear time and allows to solve many problems efficiently when the width of the decomposition tree is bounded. In this talk we survey how to generalize it to some other objects: bipartite graphs, tournaments, and hypergraphs (for the latter three variations have been proposed). Algorithmic approaches and tools to compute them are presented: top-down method, bottom-up method, and orthogonals.

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically.

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

In algorithmic enumeration, one is typically asked to output the set of all objects of a certain type related to an input (e.g. all the cycles of a graph, all its maximal cliques, etc.), rather than finding just one. The problem of enumerating all the minimal dominating sets of a graph received an important attention, partly because of its strong links with a fundamental hypergraph problem. A long standing open question is whether the above problem can be solved in (output-) polynomial time. In this talk, I will introduce the problem and present an output-polynomial algorithm for Kt-free graphs. This is joint work with Marthe Bonamy, Oscar Defrain, and Michał Pilipczuk.

Link to the article: https://arxiv.org/abs/1810.00789

Given a graph, how can one distribute resources to vertices in order to be able to respond to any infinite sequences of demands? This is the fundamental question which the study of eternal domination in graphs attempts to answer. I will give a brief survey of what is known about eternal domination, followed by recent progress on some eternal domination problems. Notably, we refute a conjecture of Klostermeyer and Mynhardt on eternal domination in prisms over graphs, and introduce a fractional version of eternal domination which to our knowledge has not yet been studied. Results were jointly obtained with D. Khatri, A. Krim-Yee, N. Kumar, G. MacGillivray, V. Virgile, and A. Xu.

Graph databases use graph structure to represent and query data. The talk will survey some graph query languages used in this context, with a focus on regular path queries (RPQs) and conjunctive regular path queries (CRPQs). We will present the different semantics that graph database systems use for them (every path, simple path, trail), and recall computational complexities of query evaluation and query containment. We will finally discuss some issues related to querying not only the topology but also the data of the graph and present a few open problems that could be of interest both to the graph and algorithms group and to the automata group.

When mining data collected from human activities, graph edges come ordered by the time instants where they are recorded, e.g. with web logs, phone calls, email exchanges, … We call this kind of data a link stream. We introduce the notion of a temporal matching (an independent temporal edge set) in a link stream. In a link stream where the time dimension is reduced to one unique time instant, our new definition is equivalent to that of a matching in classical graph theory.

In contrast to classical graph theory, we show that the problem of computing a temporal matching of maximum size in a link stream is in general NP-hard. We then depict a kernelization algorithm parameterized by the solution size for the problem, producing quadratic kernels. As a byproduct we also give a 2-approximation algorithm. Both algorithms are implemented and confronted to link streams collected from real world graph data:

https://github.com/antoinedimitriroux/Temporal-Matching-in-Link-Streams

We observe from the experiments that the kernelization algorithm can perform very well in practice, reducing the instance size downto 10-20% on realistic mining parameters. In contrast, the 2-approximation gives rather mixed results. We conjecture that the approximation factor can be improved.

For a fixed collection of graphs F, the F-DELETION problem consists in, given a graph G and an integer k, decide whether there exists S, subset of V(G), with |S| ⇐ k such that G-S does not contain any of the graphs in F as a minor. This NP-hard problem is a generalization of some well known graph problems as VERTEX COVER (F={K_2}), FEEDBACK VERTEX SET (F={K_3}), or VERTEX PLANARIZATION (F={K_5,K_{3,3}}). We are interested in its parameterized complexity when the parameter is the treewidth of G, denoted by tw. Namely, the objective is to determine, for a fixed F, the (asymptotically) smallest function f_F: N → N such that F-DELETION can be solved in time f_F(tw)*n^{O(1)} on n-vertex graphs. In this talk we will provide the basic definitions of parameterized complexity, motivate the problem, and then, review some of the lower and upper bounds on the function f_F for several instantiations of F.

The presented results are joint work with Ignasi Sau and Dimitrios Thilikos and can be found in <https://arxiv.org/abs/1704.07284>.

We consider the complexity of the \textsc{Independent Set Reconfiguration} problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the $c$-\textsc{Colorable Reconfiguration} problem under the same rule, where the constraint is now to maintain the set $c$-colorable at all times.

Joint work with Eun-Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi and Florian Sikora.

Learning on graphs requires a graph feature representation able to discriminate among different graphs while being amenable to fast computation. The graph isomorphism problem tells us that no fast representation of graphs is known if we require the representation to be both invariant to nodes permutation and able to discriminate two non-isomorphic graphs. Most graph representations explored so far require to be invariant. We explore new graph representations by relaxing this constraint. We present a generic embedding of graphs relying on spectral graph theory called Spectral Graph Embedding (SGE). We show that for a large family of graphs, our embedding is still invariant. To evaluate the quality and utility of our SGE, we apply them to the graph classification problem. Through extensive experiments, we show that a simple Random Forest based classification algorithm driven with our SGE reaches the state-of-the-art methods.

Although our SGE is handcrafted, we also show how our generic embedding technique can be learned and built in a data-driven manner opening the way to new learning algorithms and deep learning architectures with some invariant constraints built-in.

In this talk, we will discuss various results around Brooks' theorem: a graph has chromatic number at most its maximum degree, unless it is a clique or an odd cycle. We will consider stronger variants and local versions, as well as the structure of the solution space of all corresponding colorings.

This talk concerns the problem of quickly computing distances and shortest paths on distributed networks (the CONGEST model). There have been many developments for this problem in the last few year, resulting in tight approximation schemes. This left open whether exact algorithms can perform equally well. In this talk, we will discuss some recent progress in answering this question. Most recent works that this talk is based on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018).

A well-known problem for which it is difficult to improve the textbook algorithm is computing the graph diameter. We present two versions of a simple algorithm (one being Monte Carlo and the other deterministic) that for every fixed $h$ and unweighted undirected graph $G$ with $n$ vertices and $m$ edges, either correctly concludes that $diam(G) < hn$ or outputs $diam(G)$, in time ${\cal O}(m+n^{1+o(1)})$. The algorithm combines a simple randomized strategy for this problem (Damaschke, {\it IWOCA'16}) with a popular framework for computing graph distances that is based on range trees (Cabello and Knauer, {\it Computational Geometry'09}). We also prove that under the Strong Exponential Time Hypothesis (SETH), we cannot compute the diameter of a given $n$-vertex graph in truly subquadratic time, even if the diameter is an $\Theta(n/\log{n})$.

In this talk, I will present a framework combining the rank-based approach with the notion of $d$-neighbor equivalence. The rank-based approach is a technique introduced by Bodlaender et al. in 2015 to obtained $2^{O(k)}\cdot n$ time algorithms, $k$ the treewidth of the input graph, for a wide range of connectivity problems.

The $d$-neighbor equivalence is a tools introduced by Bui-Xuan et al. in 2013 to obtained efficient parameterized algorithms for many width measures (clique-width, rank-width, mim-width,…) and for many problems with a locally checkable constraint (Dominating Set, Independent Set,…).

By combining these two notions, we obtain efficient algorithms for several connectivity problems such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, $\mathbb{Q}$-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the best time complexity for Vertex Cover and Dominating Set.

Paper available on HAL : https://hal.archives-ouvertes.fr/hal-01799573v2/document

A \textit{unique-maximum} coloring of a plane graph is a proper vertex coloring by natural numbers where on each face $\alpha$ the maximal color appears exactly once on the vertices of $\alpha$. Fabrici and G\“{o}ring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five.

We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. So, we conclude that the facial unique-maximum chromatic number of the sphere is not four but five.

Additionally, we will consider a facial edge-coloring analogue of the aforementioned coloring, and we will conclude the talk with various open problems.

(Joint work with Vesna Andova, Bernard Lidick\'y, Borut Lu\v{z}ar, and Kacy Messerschmidt)

We consider Gallai's graph Modular Decomposition theory for network analytics. On the one hand, by arguing that this is a choice tool for understanding structural and functional similarities among nodes in a network. On the other, by proposing a model for random graphs based on this decomposition. Our approach establishes a well defined context for hierarchical modeling and provides a solid theoretical framework for probabilistic and statistical methods. Theoretical and simulation results show the model acknowledges scale free networks, high clustering coefficients and small diameters all of which are observed features in many natural and social networks.

Informally, a set operad is a family of combinatorial structures plus 1) an (associative) mechanism that creates larger structures from smaller using as assembler an external structure in the same family 2) Identity structures over singleton sets. We give the precise definition of set operads in the context of Joyal’s combinatorial species. Interesting examples of set operads are Graphs, directed graphs, posets, Boolean functions, monotone Boolean functions, simple multiperson games, simplicial complexes, etc. We show that Decompositions theory of combinatorial structure can be formulated in the general context of set operads by using the operation of amalgam (coproduct) of operads.

In coalition formation games, self-organized coalitions are created as a result of the strategic interactions of independent agents. For each couple of agents $(i,j)$, weight $w_{i,j}=w_{j,i}$ reflects how much agents $i$ and $j$ benefit from belonging to the same coalition. We consider the modified fractional hedonic game, that is a coalition formation game in which agents' utilities are such that the total benefit of agent $i$ belonging to a coalition (given by the sum of $w_{i,j}$ over all other agents $j$ belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games.

We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions, leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0-1 weights.

It is well known that you can color a graph G of maximum degree d greedily with d+1 colors. Moreover, this bound is tight, since it is reached by the cliques. Johansson proved with a pseudo-random coloring scheme that you can color triangle-free graphs of maximum degree d with no more than O(d/log d) colors. This result has been recently improved to (1+ε)(d/log d) for any ε>0 when d is big enough. This is tight up to a multiplicative constant, since you can pseudo-randomly construct a family of graphs of maximum degree d, arbitrary large girth, and chromatic number bigger than d / (2 log d). Although these are really nice results, they are only true for big degrees, and there remains a lot to say for small degree graphs. When the graphs are of small degree, it is interesting to consider the fractional chromatic number instead, since it has infinitely many possible values – note that cubic graphs are either bipartite, the clique K4, or of chromatic number 3. It has already been settled that the maximum fractional chromatic number over the triangle-free cubic graphs is 14/5. I will present a systematic method to compute upper bounds for the independence ratio of graphs of given (small!) degree and girth, which can sometimes lead to upper bounds for the fractional chromatic number, and can be adapted to any family of small degree graphs under some local constraints.

Abstract : Assume we are given a graph G=(V,E) (directed or not) with capacities and costs on the edges, a vertex r of G called root, and a set X of terminal vertices. The problem we consider is the following: find in G a minimum-cost tree rooted at r, spanning all the vertices in X, and such that, for each edge of this tree, the number of paths going from r to terminals and containing this edge does not exceed its capacity. When all capacities are at least |X|, then this is the classical Steiner tree problem, with a given root. The generalization we are interested in has several relevant applications, including the design of wind farm collection networks. We study the complexity of this problem in different settings: for instance, the graph may be directed or not, |X| may be fixed or not, the costs may be 0 or not. Whenever this is possible, we also design approximation algorithms to solve the problem.

A graph H is an induced minor of a graph G if it can be obtained from an induced subgraph of G by contracting edges. Otherwise, G is said to be H-free.

We show that the class of H-free graphs is well-quasi-ordered by induced minors if and only if H is an induced minor of the gem (=the path on 4 vertices plus a dominating vertex) or the graph obtained by adding a vertex of degree 2 to the K4 (= the complete graph on 4 vertices).

This generalizes a a result of Robin Thomas who proved that K4-free graphs are well-quasi-ordered by induced minors and complements similar dichotomy theorems proved by Guoli Ding for subgraphs and Peter Damaschke for induced subgraphs.

This is joint work with Jarosław Błasiok, Jean-Florent Raymond, and Théophile Trunck.

La méthode topologique est la seule méthode connue pour déterminer le nombre chromatique de certaines classes de graphes, et un problème classique est d’obtenir des preuves alternatives plus élémentaires. Après une brève introduction à la méthode topologique, je présenterai certains de mes travaux qui y sont liés et j’expliquerai pourquoi le recours à la topologie est parfois difficilement évitable.

The computation of several graph measures, based on the distance between nodes, is very often part of the analysis of real-world complex networks. The diameter, the betweenness and the closeness centrality, and the hyperbolicity are typical examples of such measures. In this talk, we will focus on the computation of one specific measure, that is, the node closeness centrality which is basically the inverse of the average distance of a node from all other nodes of the graph. Even though polynomial-time algorithms are available for the computation of this measure, in practice these algorithms are not useful, due to the huge size of the networks to be analysed. One first theoretical question is, hence, whether better algorithms can be designed, whose worst-case complexity is (almost) linear in the size of the input graph. We will first show that, unfortunately, for the closeness centrality no such algorithm exists (under reasonable complexity theory assumptions). This will lead us back to the practical point of view: we will then describe a heuristics that allows us to compute the above measure in (practical) linear time, even though its worst-case complexity is (in practice) intractable. This result will finally motivate our return to theory in order to understand the reason why, in practice, this heuristics works so well: we will indeed conclude by showing that, in the case of several random graph generating models, the average time complexity of the heuristics is indeed (almost) linear. This talk will summarise the research work that I have done in collaboration with Elisabetta Bergamini, Michele Borassi, Michel Habib, Andrea Marino, Henning Meyerhenke, and Luca Trevisan, and will be mostly based on two papers presented at ALENEX 2016, and SODA 2017.

Savoir qu’une classe de structures est caractérisée par une liste finie d’obstructions n’est pas toujours satisfaisante pour reconnaître les membres de la classe et il est souvent désirable pour un algorithme de reconnaissance de fournir un certificat de non appartenance. Dans cet exposé, j’expliquerai quelques aspects de mes travaux sur le calcul des obstructions pour certaines classes de matroides.

Dans cet exposé j'expliquerai plusieurs de mes travaux sur différents modèles de graphes aléatoires : en particulier, je vais expliquer les périodes de connexité d'un modèle dynamique des graphes géométriques Euclidiens, la rigidité et l'orientabilité du graphe G(n,p), et je parlerai (de résultats sur) des graphes aléatoires hyperboliques et d'applications pour des grands réseaux.

Tree-width and clique-width are well-known graph parameters of algorithmic use. Clique-width is a stronger parameter in the sense that it is bounded on more classes of graphs. In this talk we will present an even stronger graph parameter called mim-width (maximum induced matching-width). Several nicely structured graphs, like interval graphs, permutation graphs and leaf power graphs, have mim-width 1. Given a decomposition of bounded mim-width of a graph G we can solve many interesting problems on G in polynomial time. We will mention also a yet stronger parameter, sim-width (special induced matching-width), of value 1 even for chordal and co-comparability graphs.

Parts of the talk are based on joint work with O.Kwon and L.Jaffke, to appear at STACS 2018.

Local-search is an intuitive approach towards solving combinatorial optimization problems: start with any feasible solution, and try to improve it by local improvements. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a locally optimal solution. In this talk I will present the ideas and techniques behind the use of local-search in the design of provably good approximation algorithms for some combinatorial problems, such as independent sets, vertex cover, dominating sets in geometric intersection graphs. The key unifying theme is the analysis of local expansion in planar graphs. Joint work with Norbert Bus, Shashwat Garg, Bruno Jartoux and Saurabh Ray.

Graph rewriting formalisms are well-established models for the representation of biological systems such as protein-protein interaction networks. The combinatorial complexity of these models usually prevents any explicit representation of the variables of the system, and one has to rely on stochastic simulations in order to sample the possible trajectories of the underlying Markov chain. The bottleneck of stochastic simulation algorithms is the update of the propensity function that describes the probability that a given rule is to be applied next. In this talk we present an algorithm based on a data structure, called extension basis, that can be used to update the counts of predefined graph observables after a rule of the model has been applied.

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg

Given, at each time t = 1, 2, …, n, a new file of length l(t) and a read rate r(t), an online k-compaction algorithm must maintain a collection of at most k files, choosing (at each time t, without knowing future inputs) some of the files to merge into one, thereby incurring a merge cost equal to the total length of the merged files and a read cost equal to the read rate r(t) times the number of files present at time t. The goal is to minimize the total cost over time. K-compaction algorithms are a key component of log-structured merge trees, the file-based data structure underlying NoSQL databases such as Accumulo, Bigtable, Cassandra, HBase,and others. We initiate the theoretical study of k-compaction algorithms. We formalize the problem, consider worst-case, average-case and competitive analysis (per-instance optimality), and propose new algorithms that are optimal according to these metrics.

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.

For the game of cops and robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time and that there exist graphs in which this capture time is tight. When k ≥ 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O( n^(k+1) ), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. We answer the question of Bonato and Nowakowski on the negative, proving that the O(n^(k+1) ) bound is asymptotically tight for any constant k ≥ 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.

In this talk, we focus on two different aspects of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PLS) model defines a distributed proof in the form of a label that is given to each node, and all nodes locally verify that the network configuration satisfies the desired boolean predicate by exchanging labels with their neighbors. The complexity measure of the scheme, a.k.a. the proof size, is defined to be the maximum size of a label.

1. Space-time tradeoffs for distributed verification, joint work with Rafail Ostrovsky and Will Rosenbaum. In this work, we introduce the notion of a t-PLS, which allows the verification procedure to run for super-constant time. Our work analyzes the tradeoffs of t-PLS between time, label size, message length, and computation space. We construct a universal t-PLS and prove that it uses the same amount of total communication as a known one-round universal PLS, and t factor smaller labels. In addition, we provide a general technique to prove lower bounds for space-time tradeoffs of t-PLS. We use this technique to show an optimal tradeoff for testing that a network is acyclic (cycle free). Our optimal t-PLS for acyclicity uses proof size, message size and computation space O( ( log n)/t).

2. Approximate proof-labeling schemes, joint work with Keren Censor-Hillel and Ami Paz. In this work we extend the PLS model by defining the approximate PLS (APLS) model. In this new model, the predicates for verification are of the form f(G)\le f'(G), where f, f': F → N for a family of configurations F and the set of natural numbers N. Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration alpha, so that only if f(G) > alpha*f'(G) some node must reject. We show that in the APLS model, the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size.

We provide an efficient algorithm for determining how a road network has evolved over time, given two snapshot instances from different dates. To allow for such determinations across different databases and even against hand drawn maps, we take a strictly topological approach in this paper, so that we compare road networks based strictly on graph-theoretic properties. Given two road networks of same region from two different dates, our approach allows one to match road network portions that remain intact and also point out added or removed portions. We analyze our algorithm both theoretically, showing that it runs in polynomial time for non-degenerate road networks even though a related problem is NP-complete, and experimentally, using dated road networks from the TIGER/Line archive of the U.S. Census Bureau.

Can you tell me how long should be the talk?

In this talk, i will present first some theorems and observations about matching in cubic graphs and about covering the edges of cubic graphs by perfect matchings. Then I will present some interesting open problems in this area.

A k-dicolouring of a digraph is a partition of its vertex setinto k acyclic subdigraphs. The dichromatic number of a digraph D is the minimum k such that D has a k-dicolouring.

We first give some properties related to the dichromatic number in order to show why and how it generalizes the chromatic number of non-oriented graphs. Then we investigate the following questions: What can we say about subgraphs, induced subgraphs and topological minors of a digraph with large dichromatic number?

The Lovasz Local Lemma, a cornerstone of the probabilistic method, is a powerful and widely used proof technique. In 2009, Moser introduced a technique called entropy compression to provide efficient algorithms which construct objects that the Local Lemma guarantees to exist. Recently, entropy compression has been used to develop more powerful versions of the Local Lemma which provide existence proofs in settings where the original Local Lemma does not apply. I will illustrate this technique with applications to graph colouring: (a) colouring triangle-free graphs, and (b) frugal colouring, where no colour can appear too many times in any neighbourhood.

Guerraoui and Ruppert introduced the model of Community Protocols. This Distributed System works with agents having a finite memory and unique identifiers (the set of identifiers being ordered). Each agent can store a finite number of identifiers they heard about. The interactions are asynchronous and pairwise, following a fair scheduler. The computation power of this model is fully characterized: it corresponds exactly to what non deterministic Turing Machines can compute on a space O(n\log n). In this talk, I will focus on two restrictions of the model: The first is what happens when agents may share identifiers, the population admitting homonyms. I will introduce a hierarchy, with characterizations depending on the rate of unique identifiers present in the population. The main result is that with log n identifiers, a Turing Machine with a polylogarithmic space can be simulated. The second considers the following time restriction: what can be computed in a polylogarithmic number of parallel interactions. This version is not yet characterized, but I will provide some impossibility results, some computable protocols, and I will give the tighter bound we found.

Dans cet exposé je vous présenterai les résultats obtenus au cours de ma thèse, laquelle traite de noyaux et de complexité paramétrée. La complexité paramétrée est une branche de l'algorithmie qui analyse la complexité d'un problème en fonction de la taille des données n et d'un paramètre k (arbitraire). L'objectif est de pouvoir attaquer des problèmes difficiles (NPc) et de montrer que l’exposition combinatoire n'est fonction que du paramètre (et pas de la taille des données), cad, trouver des algorithmes en f(k)+p(n). L'extraction de noyau est une méthode qui permet d'obtenir des algorithmes avec un telle complexité. Il s'agit d'un pré-calcul (une réduction polynomiale) qui réduit la taille des données en temps polynomial, tout en garantissant que la taille du noyau (l'instance réduite) est bornée par une fonction du paramètre g(k). Il suffit de résoudre le problème dans le noyau, de n'importe quelle façon, pour obtenir un algorithme en f(g(k)) + p(n).

La méthode de décomposition en régions [Alber, Fellows, Niedermeier] est un résultat majeur dans le domaine des noyaux. Elle a permis de construire de nombreux noyaux linaires pour des variantes de la Domination dans les graphes planaires. J'illustrerai cette méthode avec le cas de la Domination Rouge Bleu, qui consiste à trouver, dans un graphe bicoloré, un ensemble de sommets bleus tel que tous les sommets rouges sont à distance au plus 1 de la solution.

Cette méthode a ensuite été généralisée par des méta-résultats [ex: Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos], qui prouve l'existence de noyaux (dans des graphes peu denses) pour tout problème vérifiant certaines conditions génériques. Je présenterai un de ses méta-résultats, qui se base sur la programmation dynamique et sur la décomposition en protrusion, et qui a le mérite d’être constructif.

I will survey and try to explain the intuition behind several recent developments in the theory of distributed graph algorithms. I will focus on the LOCAL model, where the measure of interest is how far information has to be propagated in a communication network in order solve a given problem. The problems of interest will be locally checkable labelling problems (LCLs), a natural class of problems that allow distributed verification of proposed solutions.

I will discuss two recent papers in this field. First, we gave a lower bound showing that there exist LCL problems of ”intermediate” complexity, that is, complexity strictly between known complexity classes (Brandt et al., STOC 2016). The proof is by a new kind of simulation argument. Second, Chang et al. (FOCS 2016) showed that this lower bound implies an exponential separation between the randomized and deterministic LOCAL models. Chang et al. also show further connections between the randomized and deterministic models, and establish a useful speed-up simulation for the deterministic LOCAL model.

We will present algorithms for the evacuation problem by a pair of distinct-speed robots on an infinite line. In this problem, two mobile robots with different maximal speeds are initially placed at the same point on an infinite line. The robots need to find a stationary target (i.e., the exit), which is placed at an unknown location on the line. The search is completed when both robots arrive at the exit and the goal is to conclude evacuation in as little time as possible. The robot that discovers the exit first may communicate it to the other robot. We consider two models of communication between the robots, namely wireless communication and face-to-face communication. We present an optimal algorithm for any combination of robot speeds in the case of face-to-face communication. In the case of wireless communication, our algorithm is optimal if the slow robot is at most 6 times slower than the fast robot.

Joint work with Adrian Kosowski

The goal of a hub-based distance labeling scheme for a network $G = (V, E)$ is to assign a small subset $S(u) \subseteq V$ to each node $u \in V$, in such a way that for any pair of nodes $u, v$, the intersection of hub sets $S(u) \cap S(v)$ contains a node on the shortest $uv$-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least $r$ intersecting a given ball of radius $2r$. In this talk, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.

We are interested in the following problem: Given a collection of n objects in the plane and an integer k, is there a proper k-coloring of its intersection graph (i.e., such that two overlapping objects get different colors). Here we think of k as a function of n; it can be constant, linear, or anything in between. From an application of a known separator theorem, if the input objects are fat (i.e., have bounded diameter/width ratio), then this problem can be solved in time 2^{O(\sqrt{n k} \log n)}. We will show that this running time is essentially optimal under the Exponential Time Hypothesis (ETH). We then move to intersection graphs of segments (which are quintessentially non fat) and show that the situation is quite different than with fat objects. We end on a surprising note: 3-coloring and 4+-coloring of segments have significantly different behaviors.

The guideline and motivation of the talk is to go beyond the NP-hardness of coloring those geometric graphs, and precise what is the best (hopefully subexponential) running time that we can get.

This is based on a joint work with Csaba Biró, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski, and an ongoing project with Stéphan Thomassé and a subset of the aforementioned authors.

Real-world graphs (a.k.a. complex networks) are ubiquitous: the web, Facebook, Twitter, brain networks, protein interaction networks, etc. Studying these graphs and solving computational problems on them (say maximum clique, partitioning or dense subgraph) has applications in many fields. I will first show that the structure of some real-world graphs is special. In particular, they are not adversarial and some difficult problems (say NP-complete or NP-hard problems) can be solved on some huge real-world graphs (say 2G edges or more). I will then present two works along the lines of “understanding and leveraging the structure of real-world graphs in order to build better algorithms”: (i) Enumerating all k-cliques and (ii) Computing the density-friendly graph decomposition.

Given a graph G with a coloring, a Kempe chain of G is a maximal connected subgraph of G in which each vertex has one of two colors. A Kempe change is the operation of swapping the colors of a Kempe chain. Two colorings are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. In this talk, we survey some of the existing results, open problems and common proof techniques in this area.

The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. Reed proved in 1998 that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. A key step in the proof deals with how to spare colors in a graph whose every vertex “sees few edges” in its neighborhood. We improve the existing approach, and discuss its applications to Reed's theorem and strong edge coloring.

This is joint work with Thomas Perrett (Technical University of Denmark) and Luke Postle (University of Waterloo).

How efficiently can we find an unknown graph using shortest path queries between its vertices? This is a natural theoretical question from the standpoint of recovery of hidden information. This question is related to discovering the topology of Internet networks, which is a crucial step for building accurate network models and designing efficient algorithms for Internet applications.

In this talk, I will introduce the problems of graph reconstruction and verification via oracles. I will investigate randomized algorithms based on a Voronoi cell decomposition. I will also analyze greedy algorithms, and prove that they are near-optimal.

The talk is based on joint work with Claire Mathieu and Sampath Kannan.

Joint work with Derek Corneil, Jérémie Dusart and Ekkehard Kh\“oler

A cocomparability graph is a graph whose complement admits a transitive orientation. An interval graph is the intersection graph of a family of intervals on the real line. In this paper we investigate the relationships between interval and cocomparability graphs. I will first present some recent algorithms we obtained on cocomparability graphs. They show that for some problems, the algorithm used on interval graphs can also be used with small modifications on cocomparability graphs. Many of these algorithms are based on graph searches that preserve cocomparability orderings.

Then I will propose a characterization of cocomparability graphs via a lattice structure on the set of their maximal cliques. Using this characterization we can prove that every maximal interval subgraph of a cocomparability graph $G$ is also a maximal chordal subgraph of $G$.

This characterization also has interesting algorithmic consequences and we show that a new graph search, namely Local Maximal Neighborhood Search (LocalMNS) leads to an $O(n+mlogn)$ time algorithm to find a maximal interval subgraph of a cocomparability graph. Similarly I propose a linear time algorithm to compute all simplicial vertices in a cocomparability graph. In both cases we improve on the current state of knowledge.

Je présenterai un algorithme autostabilisant pour réseaux overlay construisant le graphe d'une métrique donnée par oracle. L'algorithme fonctionne sous les daemons synchrones et asynchrones. Sous daemon synchrone le temps de convergence est linéaire. Dans tout les cas, la complexité en messages et celle en mémoire sont aussi faibles que possible. Cette construction peut être utilisée pour construire pour de la construction d'un graphe arbitraire.

The notion of rank of divisor on graph was introduced by Baker and Norine in 2007 in showing the link with the similar notion on Riemann surface. Moreover, the authors have developed a theorem for divisors on graph analogue to the classical Riemann-Roch theorem. Since then, many works have studied for computing the rank of divisors on graph. A very important is the new theorem on the NP-hardness complexity of the Problem of computing the rank of divisor on general graph. The proof of this result was based on the proof of the NP-hardness of the Problem of finding the minimum recurrent configurations of Chip Firing Game on directed graphs (by Perrot and Pham). In this talk, we will present some (linear) algorithms for computing the rank of divisors on some classes of graphs.

A Research-Mantra is something “cosmic” one believes holds in the area of research at hand. It is then a “pillar of fire” in front that leads the way. The Mantra is to be followed as long as it is not refuted by facts.
In this talk I'll present some Mantras I followed during the years starting with one that says that Distributed-Computing Theory (DCT) is the Mathematical Study of Interleaving. Consequently, DCT researchers should have Mathematical sensibilities rather than Engineering ones. Thus, DCT should poses the beauty of Mathematics, and should not be be “hacked” as an Engineering Domain. In particular any paper that points to “anomalies” or “paradoxes” does not point to faults in the domain but to faults in the thinking of the authors. I'll show some Mantras I use and where they led, and I'll end up with the ramification of recent Mantra that holds that deterministic state-machines capture interleaving as well as message-passing interleaving.

We study the fundamental problem of counting, which consists in computing the size of a system. The considered model are population protocols, which is the model of finite state, anonymous and asynchronous mobile devices (agents) communicating in pairs (according to a fairness condition). We significantly improve the previous results known for counting in this model, in terms of (exact) space complexity. Specifically, we give the first space optimal protocols solving the problem for two classical types of fairness, global and weak. Both protocols require no initialization of the counted agents. The protocol designed for global fairness, surprisingly, uses only one bit of memory (two states) per counted agent. The protocol, functioning under weak fairness, requires the necessary log P bits (P states, per counted agent) to be able to count up to P agents. Interestingly, this protocol exploits the intriguing Gros sequence of natural numbers, which is also used in the solutions to the Chinese Rings and the Hanoi Towers puzzles.

We give a proof of Enomoto's conjecture for graphs of sufficiently large order. Enomoto's conjecture states that: if G is a graph of order n with minimum degree at least n/2+ 1, then for any pair x,y of vertices of G, there is a Hamiltonian cycle C of G such that the distance between x and y in C is n/2.

The main tools of our proof are Regularity Lemma of Szemeredi and Blow-up Lemma of Koml os et al..

This is a joint work with Weihua He and Hao Li.

Recent empirical and theoretical work has suggested that many real-life complex networks and graphs arising in Internet applications, in biological and social sciences, in chemistry and physics have tree-like structures from a metric point of view. A number of graph parameters trying to capture this phenomenon and to measure these tree-like structures were proposed; most notable ones being the tree-stretch, tree-distortion, tree-length, tree-breadth, Gromov’s hyperbolicity of a graph, and cluster-diameter and cluster-radius in a layering partition of a graph. If such a parameter is bounded by a constant on graphs then many optimization problems can be efficiently solved or approximated for such graphs. We discuss these parameters and recently established relationships between them for unweighted and undirected graphs; it turns out that all these parameters are at most constant or logarithmic factors apart from each other. We give inequalities describing their relationships and discuss consequences for some optimization problems.

We will provide (two) new proof(s) of Seymour's 6-flow theorem (both) using induction.

Nicolas Schabanel, joint work with Cody Geary (Caltech), Pierre-Étienne Meunier (U. Aalto), et Shinnosuke Seki (U. Electro-Communications, Tokyo).

We introduce and study the computational power of Oritatami, a theoretical model to explore greedy molecular folding, by which the molecule begins to fold before waiting the end of its production. This model is inspired by our recent experimental work demonstrating the construction of shapes at the nanoscale by folding an RNA molecule during its transcription from an engineered sequence of synthetic DNA. While predicting the most likely conformation is known to be NP-complete in other models, Oritatami sequences fold optimally in linear time. Although our model uses only a small subset of the mechanisms known to be involved in molecular folding, we show that it is capable of efficient universal computation, implying that any extension of this model will have this property as well.

We introduce general design techniques for programming these molecules. Our main result in this direction is an algorithm in time linear in the sequence length, that finds a rule for folding the sequence deterministically into a prescribed set of shapes depending of its environment. This shows the corresponding problem is fixed-parameter tractable although we proved it is NP-complete in the number of possible environments. This algorithm was used effectively to design several key steps of our constructions.

We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted graphs and which we use in a multisweep algorithm to recognize Robinsonian matrices. Since Robinsonian binary matrices correspond to unit interval graphs, our algorithm can be seen as a generalization to weighted graphs of the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. This new recognition algorithm is extremely simple and, for an n×n nonnegative matrix with m nonzero entries, it terminates in n−1 SFS sweeps, with overall running time O(n^2+nmlogn).

Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d'arêtes ne pouvant pas simultanément faire partie d'un sous-graphe), dans lesquels nous étudierons différents types de problèmes, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l'ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de NP-complétude, et des conditions suffisantes assurant l'existence de certains objets (arbre couvrant, chemin et cycle Hamiltonien) sans conflits.

The real and complex roots of chromatic polynomials, which we call chromatic roots, have been studied since the 1940s yet it is not well understood how structural properties of graphs affect their chromatic roots. In this talk we survey some results and open problems, and present recent work on the following question: For a minor- closed class of graphs, what is the infimum of the non-trivial real chromatic roots of the graphs in that class?

Hadwiger conjectured that every graph with no K_t minor is (t-1)-colorable; in other words, every graph with no K_t minor admits a partition of its vertex set into t-1 independent sets. This conjecture is still widely open and if true, it implies the four color theorem. Gerards and Seymour made a stronger conjecture claiming that every graph with no K_t odd minor is (t-1)- colorable, commonly called the odd Hadwiger's conjecture. We prove variants of Hadwiger's conjecture. First, we prove that every graph with no K_t minor admits a partition of its vertex set into t-1 sets, each inducing a subgraph of bounded maximum degree. Secondly, we prove that every graph with no K_t minor admits a partition of its vertex set into 3(t-1) sets, each inducing a subgraph having no large components.

We also prove variants of the odd Hadwiger's conjecture as follows: Every graph with no odd K_t minor admits a partition of its vertex set into 7t-10 sets, each inducing a subgraph of bounded maximum degree. As a corollary, we prove that every graph with no odd K_t minor admits a partition of its vertex set into 16t-19 sets, each inducing a subgraph with no large components. The last result improves the result of Kawarabayashi, who showed it with 496t sets.

This talk is a combination of three works; first with K. Edwards, D. Kang, J. Kim, and P. Seymour, second with C. Liu, and third with D. Kang.