Graphes Mardi 3 décembre 2019, 14 heures, Salle 1007 Marc Heinrich Counting independent sets in strongly orderable graphs 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. Graphes Mardi 26 novembre 2019, 14 heures, Salle 1007 Denis Cornaz (Université Paris Dauphine) Flows in signed graphs 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. Graphes Mardi 12 novembre 2019, 15 heures 30, Salle 3052 Suchismita Mishra (IITM) Strong chromatic index of unitary Cayley graphs 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. Graphes Mercredi 6 novembre 2019, 11 heures, Salle 3052 Laurent Viennot Distance labeling, Ruzsa-Szemeredi graphs and SumIndex communication complexity problem 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. Graphes Mardi 22 octobre 2019, 14 heures, Salle 3052 Michael Lampis (Universite Paris Dauphine) Finer Tight Bounds for Coloring on Clique-Width 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. Graphes Mardi 8 octobre 2019, 14 heures, Salle 3052 Fabien De Montgolfier (IRIF) Algorithms for generalized modular decomposition 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. Graphes Lundi 24 juin 2019, 11 heures, Salle 3052 Carola Doerr (CNRS, LIP6 Sorbonne University) Evolutionary Algorithms – From Theory to Practice and Back 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. Graphes Mardi 28 mai 2019, 15 heures, Salle 1007 Jean-Florent Raymond (TU Berlin) Enumerating minimal dominating sets in $K_t$-free graphs 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 Graphes Mardi 21 mai 2019, 14 heures, Salle 3052 Ben Seamone (Université de Montréal and Dawson College) Eternal domination in graphs 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. Graphes Jeudi 9 mai 2019, 15 heures, Salle 1007 Amélie Gheerbrant (IRIF) Graph query languages 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. Graphes Mardi 9 avril 2019, 14 heures, Salle 3052 Binh-Minh Bui-Xuan (LIP6) Temporal matching 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. Graphes Vendredi 22 mars 2019, 14 heures, Salle 1007 Julien Baste (Universität Ulm, Ulm, Germany) Hitting minors on bounded treewidth graphs 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>. Graphes Mardi 12 mars 2019, 14 heures, Salle 3052 Rémy Belmonte Token Sliding on Split Graphs 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. Graphes Mercredi 6 mars 2019, 11 heures, Salle 3052 Marc Lelarge (Inria & ENS Paris) Spectral embedding for graph classification 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. Graphes Mardi 19 février 2019, 14 heures, Salle 1007 Marthe Bonamy (CNRS - LABRI) Around Brooks' theorem 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. Graphes Mardi 19 février 2019, 11 heures, Salle 3052 Danupon Nanongkai (KTH) Distributed Shortest Paths, Exactly 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). Graphes Mardi 22 janvier 2019, 14 heures, Salle 3052 Guillaume Ducoffe (ICI Roumanie) Computing Giant Diameters with Breadth-First Search and Range Queries 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})$.