INRIA project-team GANG

Thematic team Theory and algorithmics of graphs

## Graphs

#### Day, hour and place

Tuesday at 2pm, room 1007

#### Contact(s)

#### Future talks

#### Past talks

Graphes

mardi 18 décembre 2018, 15h30, 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, 14h00, 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, 14h00, 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, 14h00, 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, 14h00, 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, 14h00, 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 06 avril 2018, 10h00, 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 03 avril 2018, 14h00, 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, 14h00, 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, 14h00, 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, 14h00, 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, 14h00, 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, 14h00, 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, 14h00, 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.

Graphes

mardi 12 décembre 2017, 14h00, 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

Graphes

mardi 17 octobre 2017, 14h00, 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.

#### Former seminar