Équipe-projet INRIA GANG
Équipe thématique Théorie et algorithmique des graphes

#### Jour, heure et lieu

Le mardi à 14h, salle 1007

Le calendrier des séances (format iCal).
Pour ajouter le calendrier des séances à votre agenda favori, souscrire au calendrier en indiquant ce lien.

### Prochaine séance

Graphes
Mardi 2 juin 2020, 15 heures 30, Online
Julien Baste (Universität Ulm) Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

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.

### Séances passées

#### Année 2020

Graphes
Vendredi 29 mai 2020, 14 heures, Online
Guillaume Ducoffe Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension

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.

Graphes
Mardi 14 avril 2020, 15 heures 30, Online
Pierluigi Crescenzi (IRIF) Temporal Closeness in Temporal Networks

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.

Graphes
Mardi 7 avril 2020, 15 heures 30, Online
Pierre Berge Fixed-parameter algorithms for finding small separators in graphs

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.

Graphes
Mardi 28 janvier 2020, 14 heures, Salle 3052
Ana Silva (Departamento de Matemática - Universidade Federal do Ceará) Time for coloring

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

#### Année 2019

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.

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:

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

#### Année 2018

Graphes
Mardi 18 décembre 2018, 15 heures 30, Salle 3052
Bergougnoux Benjamin (IRIF) Rank Based Approach on Graphs with Structured Neighborhood

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

Graphes
Mardi 11 décembre 2018, 14 heures, Salle 3052
Riste Škrekovski (University of Ljubljana) Some results and problems on unique-maximum colorings of plane graphs

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)

Graphes
Jeudi 29 novembre 2018, 14 heures, Salle 3014
Carenne Ludeña (Universidad Jose Tadeo Lozano) A random graph model based on the Modular decomposition of graphs

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.

Graphes
Mardi 27 novembre 2018, 14 heures, Salle 3052
Miguel Mendez Set operads and decomposition theory

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.

Graphes
Mardi 23 octobre 2018, 14 heures, Salle 3052
Yllka Velaj (CWI Amsterdam) Stable Outcomes in Modified Fractional Hedonic Games

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.

Graphes
Mardi 22 mai 2018, 14 heures, Salle 1007
François Pirot (Université de Strasbourg) Fractional chromatic number of small degree graphs and girth.

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.

Graphes
Vendredi 6 avril 2018, 10 heures, Salle 3052
Cédric Bentz Steiner trees with edge capacities.

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.

Graphes
Mardi 3 avril 2018, 14 heures, Salle 1007
Marcin Kaminski Induced minors and well-quasi-ordering

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.

Graphes
Mardi 27 mars 2018, 14 heures, Salle 1007
Matej Stehlik (Université Grenoble Alpes - GSCOP) Nombre chromatique et la méthode topologique

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.

Graphes
Mardi 20 mars 2018, 14 heures, Salle 1007
Pierluigi Crescenzi (Universite de Pise) Computing node centrality in large graphs: from theory to practice and back

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.

Graphes
Mardi 13 mars 2018, 14 heures, Salle 1007
Mamadou Kante (ISIMA) Obstructions pour certaines classes de matroides linéaires

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.

Graphes
Mardi 27 février 2018, 14 heures, Salle 1007
Dieter Mitsche (Université Nice) Aspects des Graphes Aléatoires

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.

Graphes
Mardi 20 février 2018, 14 heures, Salle 1007
Jan Arne Telle (University of Bergen) Width parameters of graphs and structured graph classes

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.

Graphes
Lundi 12 février 2018, 14 heures, Salle 3052
Nabil Mustafa (ESIEE) Local Search for Geometric Optimization Problems.

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.

#### Année 2017

Graphes
Mardi 12 décembre 2017, 14 heures, Salle 3052
Jean Krivine (IRIF) Incremental Update for Graph Rewriting

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

Séminaire commun du pole Algorithmes et Structures Discrètes

Graphes
Mardi 17 octobre 2017, 14 heures, Salle 3052
Claire Mathieu (DI - ENS) Online k-compaction

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.