AlGCo : algorithmes, graphes et combinatoire

Responsable : Emeric Gioan

Département Informatique - LIRMM

Accueil | Annonces | Membres | Projets | Visiteurs | Publications | Séminaire


Archives années 2014-2018 Organisateurs : Ignasi Sau, Marin Bougeret

Retour à la page d'accueil du séminaire

Archives : 2018-... | 2014-2018 | 2013-2014 | 2012-2013 | 2011-2012 | 2010-2011 | 2009-2010 | 2008-2009 | 2007-2008 | 2006-2007 | 2005-2006 | 2004-2005 | 2003-2004 | 2002-2003 | 2001-2002

Exposés 2014/2015, 2015/2016, 2016/2017, 2017/2018

12 juillet 2018
Cristophe Paul ()
Retour sur WG 2018

Présentation de quelques articles de WG 2018.

05 juillet 2018
Dimitrios Thilikos (Equipe AlGCo, CNRS, LIRMM)
Structure and Enumeration of K4-free links and link diagrams

We study the class L of link types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimal number of crossings or edges in a projection of L ∈ L. Further, we enumerate (both exactly and asymptotically) all connected K4-minor-free link diagrams, all minimal connected K4-minor-free link diagrams, and all K4-minor-free diagrams of the unknot.

Joint work with J. Rué and V. Velona

07 juin 2018
Remy Belmonte ()
Recent Results on the Complexity of Defective Coloring

In Defective Coloring we are given a graph G=(V,E) and two integers \chi_d, \Delta^∗ and are asked if we can partition V into \chi_d color classes, so that each class induces a graph of maximum degree \Delta^∗.

We present two sets of recent results regarding the complexity of the problem: first when the input graph is restricted to belong to some specific classes (split graphs, cographs and trivially perfect graphs in particular); second, when the problem is parameterized by the treewidth, pathwidth, tree-depth, or feedback vertex set of the input graph.

This is a joint work with Michael Lampis and Valia Mitsou.

17 mai 2018
Jocelyn Thiebaut ()
Packing arc-disjoint cycles and triangles in tournaments

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Tournaments form a mathematically rich subclass of directed graphs with interesting structural and algorithmic properties.
Given a tournament $T$ on $n$ vertices, we explore the problems of determining if $T$ has a cycle packing (a set of pairwise arc-disjoint cycles) of size $k$ and a triangle packing (a set of pairwise arc-disjoint triangles) of size $k$. We refer to these problems as ACT and ATT, respectively.
Although the maximization version of ACT can be seen as the linear programming dual of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments which has been widely studied, surprisingly no algorithmic results seem to exist concerning the former.

In this talk, we explore the classical and parameterized complexity of both ATT and ACT. In particular, we focus on the NP-completeness of ATT and we give a vertex-linear kernel for this problem.

This is joint work with S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh and M. Zehavi.

12 avril 2018
Marthe Bonamy (Université de bordeaux)
Distributed coloring in sparse graphs with fewer colors

We are concerned with efficiently coloring sparse graphs in
the distributed setting with as few colors as possible. According to
the celebrated Four Color Theorem, planar graphs can be colored with
at most 4 colors, and the proof gives a (sequential) quadratic
algorithm finding such a coloring. A natural problem is to improve
this complexity in the distributed setting. Using the fact that planar
graphs contain linearly many vertices of degree at most 6, Goldberg,
Plotkin, and Shannon obtained a deterministic distributed algorithm
coloring n-vertex planar graphs with 7 colors in O(logn) rounds. Here,
we show how to color planar graphs with 6 colors in polylog(n) rounds.
Our algorithm indeed works more generally in the list-coloring setting
and for sparse graphs (for such graphs we improve by at least one the
number of colors resulting from an efficient algorithm of Barenboim
and Elkin, at the expense of a slightly worst complexity). Our bounds
on the number of colors turn out to be quite sharp in general. Among
other results, we show that no distributed algorithm can color every
n-vertex planar graph with 4 colors in o(n) rounds. This is joint work
with Pierre Aboulker, Nicolas Bousquet and Louis Esperet.

05 avril 2018
Pascal Ochem (Lirmm, ALGCO)
Homomorphism of planar signed graphs to unbalanced cycles.

I will recall the definition of homomorphisms of signed graphs.
For k >= 1, the unbalanced cycle UC_{2k} contains exactly one negative edge. I will show that for k >= 1, deciding a planar signed graph has a homomorphism to UC_{2k} is NP-complete.
The proof needs the fact that the classical homomorphism of planar simple graphs to a cicrcular clique with degree 3 is NP-complete, which is of independent interest.

22 mars 2018
Daniel Gonçalves (Lirmm, ALGCO)
Dushnik-Miller dimension of contact systems of d-dimensional boxes

Planar graphs are the graphs with Dushnik-Miller dimension at most three (W. Schnyder, Planar graphs and poset dimension, Order 5, 323-343, 1989). Consider the intersection graph of interior disjoint axis-parallel rectangles in the plane. It is known that if at most three rectangles intersect on a point, then this intersection graph is planar, that is it has Dushnik-Miller dimension at most three. During this talk we will this result, from the plane to $R^d$, by considering tilings of $R^d$ with axis parallel boxes, where at most $d+1$ boxes intersect on a point. Such tilings induce simplicial complexes and we will show that those simplicial complexes have Dushnik-Miller dimension at most $d+1$. This is a joint work with M.C. Francis.

08 mars 2018
Marin Bougeret (Lirmm, ALGCO)
How much does a treedepth modulator help to obtain polynomial kernels?

In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a $c$-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most $c$, where $c \geq 1$ is a fixed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs.

In this article we answer this question by finding two very natural such problems: we prove that Vertex Cover admits a polynomial kernel on general graphs for any integer $c \geq 1$, and that Dominating Set does not for any integer $c \geq 2$ even on degenerate graphs, unless $\text{NP} \subseteq \text{coNP}/\text{poly}$. For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for $c\geq 3$ and an or-cross-composition for $c = 2$. As existing results imply that Dominating Set admits a polynomial kernel on degenerate graphs for $c = 1$, our result provides a dichotomy about the existence of polynomial kernels for Dominating Set on degenerate graphs with this parameter.

This is a joint work with Ignasi Sau.

15 février 2018
Petru Valicov (Université Aix Marseille)
Cuts in matchings

In an attempt to solve the Four Color Problem, Tait conjectured that every planar cubic 3-edge-connected graph is Hamiltonian. Once this statement was disproved, several other related questions of the type "every bipartite (planar) 3-edge connected cubic graph is Hamiltonian", emerged. On the other hand the conjecture of Neumann-Lara asserting that every planar oriented graph can be vertex-partitioned into two acyclic sets, can be seen as a directed version of Tait's conjecture. In this talk we explain how all these conjectures together with other similar questions fit in the same framework related to cuts in matchings. We show then a construction of 3-edge connected oriented graph satisfying the property that for every even subgraph E, the graph obtained by contracting the edges of E is not strongly connected. This disproves a recent conjecture of Hochstättler. At the end we will provide experimental evidence for Neumann-Lara's conjecture and discuss on tools that might be helpful to search for counterexamples. Joint work with Kolja Knauer.

08 février 2018
Rémi Watrigant (Université Lyon 1)
Complexity dichotomies for a generic hypergraph problem

Given a (possibly infinite) fixed set of graphs \F, we say that a graph G overlays \F on a hypergraph H if both G and H have the same set of vertices, and if for every hyperedge S of H, the subgraph of G induced by S contains a graph from \F as a spanning subgraph. The \F-Overlay Problem asks, given a hypergraph H, to find a graph G which \F-overlays H, and, if such a graph exists, to find one with the minimum number of edges. We will first discuss the possible applications of this problem, e.g. structural biology, network design or hypergraph drawing. We will then completely characterize the complexity of the \F-Overlay Problem (P or NP-hard) depending on the family \F. Finally, for the NP-hard cases, we will also give some sufficient conditions on \F leading to either FPT or W[1]-hard problems, when parameterized by the number of edges of the graph sought.

25 janvier 2018
Claire Pennarun (Lirmm, ALGCO)
Power domination on triangular grids with triangular and hexagonal shape

The concept of power domination emerged from the problem of monitoring electrical systems. Given a graph G and a set S \subseteq V(G), a set M of monitored vertices is built as follows: at first, M contains only the vertices of S and their direct neighbors, and then each time a vertex in M has exactly one neighbor not in M, this neighbor is added to M.
The power domination number of a graph G is the minimum size of a set S such that this process ends up with the set M containing every vertex of G.
We here give some key ideas to the proofs of the exact power domination number of triangular grids with hexagonal-shaped border, and of triangular grids with triangular-shaped border.

07 décembre 2017
Stephane Bessy ()
Out-colourings of digraphs.

Joint work with N. Alon (Tel-Aviv U.) and J. Bang-Jensen (South-Denmark U.).

We study vertex colourings of digraphs so that no out-neighbourhood is monochromatic and call such a colouring an out-colouring. The problem of deciding whether a given digraph has an out-colouring with only two colours (called a 2-out-colouring) is NP-complete. We prove that, except for the Paley tournament P7 , every semicomplete digraph of minimum out-degree at
least 3 has a 2-out-colouring. Furthermore we consider the generalization of 2-out-colourings to vertex partitions (V1 , V2) of a digraph D so that each of the three digraphs induced by respectively, the vertices of V1 , the vertices of V2 and all arcs between V1 and V2 have minimum out-degree k for a prescribed integer k ≥ 1. Using probabilistic arguments we prove that there exists an absolute constant c so that every semicomplete digraph of minimum out-degree at least 2k + c.sqrt(k) has such a partition.

23 novembre 2017
Pascal Ochem ()
H-coloring dans les graphes planaires.

Pour un graphe H fixé, le problème H-coloring
demande si le graphe d'entrée G admet un homomorphisme vers H,
c'est-à-dire si un mapping m: V(G) -> v(H) tel que
si uv est une arête de G, alors m(h)m(v) est une arête de H.
Hell et Nesetril ont montré que H-coloring est polynomial
si H est biparti et NP-complet sinon.
D'abord, je donnerai le début de cette preuve.
Ensuite, on s'intéressera au cas où G est planaire : planar H-coloring.
On verra que planar H-coloring est polynomial si H est la clique à au moins 4 sommets ou le graphe de Clebsh. Aussi planar H-coloring est NP-complet si H est un cycle impair, le carré d'un cycle pair, ou l'icosaèdre.

16 novembre 2017
Daniel Gonçalves (Lirmm, ALGCO)
Planar graphs as L-intersection or L-contact graphs : part 2

Cet exposé est la suite de l'exposé ci-dessous.

Il sera possible de suivre celui-là sans avoir suivi le précédent.

En collaboration avec Lucas Isenmann et Claire Pennarun

The L-intersection graphs are the graphs that have a representation as intersection graphs of axis parallel shapes in the plane. A subfamily of these graphs are {L, |, -}-contact graphs which are the contact graphs of axis parallel L, |, and - shapes in the plane. We prove here two results that were conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs are L-intersection graphs, and that triangle-free planar graphs are {L, |, -}-contact graphs. These results are obtained by a new and simple decomposition technique for 4-connected triangulations. Our results also provide a much simpler proof of the known fact that planar graphs are segment intersection graphs.

09 novembre 2017
Marin Bougeret (Lirmm, ALGCO)
Triangle packing in (sparse) tournaments: approximation and kernelization.

Given a tournament T and a positive integer k, the C_3-Packing-T asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C_3-Packing-T did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a (1+6/(c-1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have “length” at least c. Concerning kernelization, we show that C_3-Packing-T admits a kernel with O(m) vertices, where m is the size of a given feedback arc set. In particular, we derive a O(k) vertices kernel for C_3-Packing-T when restricted to sparse instances. On the negative size, we show that C_3-Packing-T does not admit a kernel of (total bit) size O(k^{2-epsilon}) unless NP is a subset of coNP / Poly. The existence of a kernel in O(k) vertices for C_3-Packing-T remains an open question.

Joint work with Stéphane Bessy and Jocelyn Thiebaut.

26 octobre 2017
Ignasi Sau (Lirmm ALGCO and Department of Mathematics of UFC within ParGO team (Fortaleza, Brazil).)
Finding subdivisions of spindles on digraphs.

For two positive integers $k$ and $\ell$, a $(k \times \ell)$-spindle is the union of $k$ pairwise internally vertex-disjoint directed paths with $\ell$ arcs between two vertices $u$ and $v$. In this talk we are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems.

We obtain the following complexity dichotomy: for a fixed $\ell \geq 1$, finding the largest $k$ such that an input digraph $G$ contains a subdivision of a $(k \times \ell)$-spindle is polynomial-time solvable if $\ell \leq 3$, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and prove several positive and negative results.

Joint work with Júlio Araújo, Victor A. Campos, Ana Karolinna Maia,
and Ana Silva.

19 octobre 2017
Daniel Gonçalves (Lirmm, ALGCO)
Planar graphs as L-intersection or L-contact graphs

En collaboration avec Lucas Isenmann et Claire Pennarun

The L-intersection graphs are the graphs that have a representation as intersection graphs of axis parallel shapes in the plane. A subfamily of these graphs are {L, |, -}-contact graphs which are the contact graphs of axis parallel L, |, and - shapes in the plane. We prove here two results that were conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs are L-intersection graphs, and that triangle-free planar graphs are {L, |, -}-contact graphs. These results are obtained by a new and simple decomposition technique for 4-connected triangulations. Our results also provide a much simpler proof of the known fact that planar graphs are segment intersection graphs.

05 octobre 2017
Dieter Rautenbach ((Université de Ulm, Allemagne).)
Some pursuit-evasion games on graphs.

We consider variants of a pursuit and evasion game studied independently by Britnell and Wildon as well as Haslegrave. In their game, a cat has to catch an invisible mouse that moves along the edges of some graph $G$. In one of our versions, the cat receives partial information about its distance to the mouse, and we show that the cat has a winning strategy if and only if $G$ is a forest. In a second version, we study how well the cat can localize the mouse.

The results are joint work with Moritz Schneider and Dennis Dayanikli

28 septembre 2017
pas de séminaire (25 ans du Lirmm) ()


21 septembre 2017
Marcin Pilipczuk (Faculty of Mathematics, Informatics and Mechanics of University of Warsaw.)
Recent progress in distance and cut sparsifiers.

In the talk I will discuss two related notions with regards to graph compression.
- Given a graph (directed or undirected, weighted or unweighted) G with n vertices, and a set P of p pairs of vertices, a distance sparsifier is an edge-minimal subgraph of G that maintains the same lengths of shortest paths between the pairs in P. A natural question is to obtain as small as possible size of a distance sparsifier, expressed as a function of n and p.
- Given an edge-weighted graph G with a set Q of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class.
In many special cases, the known upper and lower bounds for the above concepts are surprising far from each other. In the talk, I will survey these areas, with emphasize on open problems. Furthermore, I will present our recent result obtained in a joint work with Nikolai Karpov and Anna Zych-Pawlewicz, namely an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2^{k−2} edges in any mimicking network.

19 septembre 2017
réunion DEMOGRAPH ()


14 septembre 2017
pas de séminaire (cours Petr Golovach) ()


15 juin 2017
William Lochet (ENS Lyon)
A proof of the Erd\H{o}s-Sands-Sauer-Woodrow conjecture. Transparents de l'exposé

A very nice result of B\'ar\'any and Lehel asserts that every finite subset $X$ or $\mathbb R^d$ can be covered by $f(d)$ $X$-boxes (i.e. each box has two antipodal points in $X$). As shown by Gy\'arf\'as and P\'alv\H{o}lgyi this result would follow from the following conjecture : If a tournament admits a partition of its arc set into $k$ quasi orders, then its domination number is bounded in terms of $k$. This question is in turn implied by the Erd\H{o}s-Sands-Sauer-Woodrow conjecture : If the arcs of a tournament $T$ are colored with $k$ colors, there is a set $X$ of at most $g(k)$ vertices such that for every vertex $v$ of $T$, there is a monochromatic path from $X$ to $v$. We give a short proof of this statement. We moreover show that the general Sands-Sauer-Woodrow conjecture (which as a special case implies the stable marriage theorem) is valid for directed graphs with bounded stability number. This conjecture remains however open.

08 juin 2017
Christophe Paul (Lirmm, ALGCO)
Connected search against a lazy robber

Abstract: The node search game against a lazy/agile (invisible) robber has been introduced as a search-game analogue of the graph parameters of treewidth/pathwidth. In the “connected” variants of the above two games, we additionally demand that, at each moment of the search, the “clean” territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected pathwidth and has been shown that its value cannot be more than the double (asymptotically) of its non-connected counterpart. This implied that the “price of connectivity” is bounded by 2 for the case of an agile robber. In this paper we initiate the study of the connected variant of this search game where the robber is lazy, in the sense that he/she moves only when the searchers strategy threatens the location that he/she currently occupies. We introduce two alternative graph-theoretical formulations of its monotone variant, one in terms of (connected) layouts and one on terms of (connected) tree decompositions, leading to the graph parameter of connected treewidth. For this “lazy-robber” variant we prove that there is no bound in the price of connectivity, which comes in contrast to the case of an agile robber. We also observe that the corresponding parameter, i.e. connected treewidth, is closed under contractions and we study the contraction-obstruction set class of the class of graphs with connected treewidth at most k. It follows that this set is infinite for every k ≥ 2. We also provide a complete characterisation for the case where k = 2. This is joint work with Isolde Adler and Dimitrios M. Thilikos.

01 juin 2017
Jorgen Bang-Jensen (IMADA, University of Southern Denmark, Odense, Denmark)
Completing partial orientations to digraphs with special properties

A mixed graph is a graph which may contain both (unoriented) edges
and arcs. We denote such a graph by M = (V, E ∪ A), where E is the set of
unoriented edges and A, the set of arcs, that are already oriented. Let C be a class of digraphs, e.g. C could be the class of acyclic digraphs, tournaments, strong digraphs, digraphs with k-disjoint out-branchings etc. The Orientation completion problem for the class C is the following: given a mixed graph M = (V, E ∪ A); decide whether it is possible to orient the edges of E the a set of arcs A in such a way that the resulting digraph D = (V, A ∪ A) belongs to the class C?
Many problems fit into this framework, such as:
• Given a mixed graph M = (V, E ∪ A) which is strongly connected (when
we allow each edge in E to be traversed in any direction). Can we complete
the orientation such that we obtain a strong digraph.
• Same problem as above but now we want to preserve high edge-connectivity.
• Again the same but now we want to preserve high vertex connectivity
• Given an acyclic mixed graph M = (V, E ∪A) (meaning that A induces an
acyclic digraph) and a vertex s; can we complete the orientation so that
we obtain an acyclic digraph with an out-branching from s?
• Given an acyclic mixed graph M = (V, E ∪ A) and two vertices s, t; can
we complete the orientation so that we obtain an acyclic digraph with an
(s, t)-path?
I will discuss these and several other problems in my talk.

17 mai 2017
DeMoGraph ()
Réunion de lancement de l'ANR DeMoGraph

Réunion de lancement de l'ANR DeMoGraph

27 avril 2017
Journée Gotha, ANR Robust ()
GoTHA workshop on robust scheduling


20 avril 2017
Claire Pennarun (LABRI, Bordeaux, France)
Compter les orientations eulériennes

Nous commencerons par détailler la construction classique des cartes Eulériennes planaires et par proposer une variante de cette construction.
Les cartes Eulériennes planaires sont des objets combinatoires bien connus et leur nombre a une expression simple.
Si maintenant on veut orienter ces cartes de manière "Eulérienne", c'est-à-dire que pour tout sommet, les degrés entrant et sortant sont égaux, alors on obtient la famille des orientations eulériennes planaires (PEO). Nous allons voir pourquoi les décompositions classiques ne permettent pas de trouver directement la série génératrice des PEO. Nous montrerons comment "contourner" ce problème en définissant des sur- et sous-familles des PEO, qui elles possèdent des séries génératrices calculables et même algébriques.

30 mars 2017
Lucas Isenmann (Lirmm, ALGCO)
Dushnik-Miller dimension of TD-Delaunay complexes

TD-Delaunay graphs, where TD stands for triangle-distance, are obtained from a variation of Delaunay triangulation consisting in replacing circles by homothetic triangles. It was noticed that every triangulation is the TD-Delaunay graph of a set of points in R^2, and conversely. It seems natural to study the generalization of this property in higher dimensions. Such a generalization is obtained by replacing equilateral triangles by regular simplexes in dimension R^d. The abstract simplicial complexes obtained from a TD-Delaunay complex in dimension d are of Dushnik-Miller dimension d + 1. The converse holds for d = 2 and 3 and it was conjectured to hold for larger d. Our work with Daniel Gonçalves is to disprove the conjecture already for d = 4.

09 mars 2017
Eunjung kim (CNRS / Lamsade, Paris)
A polynomial kernel for Distance-Hereditary Vertex Deletion

A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both ver- tices is the same as their distance in the original graph. The Distance- Hereditary Vertex Deletion problem asks, given a graph G on n vertices and an integer k, whether there is a set S of at most k vertices in G such that G − S is distance-hereditary. This problem is impor- tant due to its connection to the graph parameter rank-width; distance- hereditary graphs are exactly graphs of rank-width at most 1. Eiben, Ganian, and Kwon (MFCS’ 16) proved that Distance-Hereditary Ver- tex Deletion can be solved in time 2O(k)nO(1), and asked whether it admits a polynomial kernelization. We show that this problem admits a polynomial kernel, answering this question positively. For this, we use a similar idea for obtaining an approximate solution for Chordal Ver- tex Deletion due to Jansen and Pilipczuk (SODA’ 17) to obtain an approximate solution with O(k3 log n) vertices when the problem is a Yes-instance, and we exploit the structure of split decompositions of distance-hereditary graphs to reduce the total size.

23 février 2017
Mordo Shalom (Department of Computer Science, Tel-Hai College, Upper Galilee, Israel)
A Polynomial-time Algorithm for the Maximum Cardinality Cut Problem in Proper Interval Graphs

It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.

02 février 2017
Arnaud Sallaberry (LIRMM, équipe ADVANSE)
Hypergraphes planaires : résultats et problème ouvert

Un hypergraphe est une paire H=(V,A) où V est un ensemble de sommets et A est un ensemble de sous-ensembles non vides de V. Une approche classique pour représenter graphiquement un hypergraphe consiste à dessiner les sommets sous forme de points et les hyperarêtes sous forme de polygones. Le principal enjeu consiste alors à trouver un positionnement des sommets tel que les intersections des polygones dans le plan ne contienne que les sommets des hyperarêtes correspondant à ces polygones. La notion d'hypergraphe planaire a été introduite pour caractériser les hypergraphes pouvant être dessinés de cette façon. Plusieurs définitions formelles ont été proposées. La plus générale est basée sur la notion de support. Un graphe support d'un hypergraphe H=(V,A) est un graphe G=(V,E) dans lequel les sous-graphes induits par les sommets de chaque hyperarête sont connexes. Un hypergraphe est dit planaire si et seulement si il possède un graphe support planaire. Dans cet exposé, je présenterai plusieurs problèmes résolus et un ouvert liés à la planarité des hypergraphes. Plusieurs de ces résultats reposent sur une nouvelle définition des composantes bi-connexes d'un hypergraphe.

26 janvier 2017
Stéphane Bessy (Lirmm, ALGCO)
Extremal values of the chromatic number for a given degree sequence

joint work with D. Rautenbach (Ulm University, Germany)

Pour une séquence de degrés d: d1 >= d2 >= ... >= dn, on définit Xmax(d) (resp. Xmin(d)) le plus grand (resp. plus petit) nombre chromatique d'un graphe de séquence de degrés d.

Après avoir motivé l'étude de ces invariants (d'un point de vue théorique ainsi qu'applicatif -hum...-), puis présenté les grands résultats connus sur les réalisations de séquences de degrés, je donnerai les résultats théoriques et algorithmiques que nous avons obtenus pour borner ou calculer Xmax et Xmin.

19 janvier 2017
Emeric Gioan (Lirmm, ALGCO)
On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges)

I will present six interrelated general expressions of the Tutte polynomial of a graph, that are available as soon as the set of edges is linearly ordered, and that witness combinatorial properties of such a graph:

- the classical enumeration of spanning tree activities;

- its refinement into a four variable expression in terms of subset activities (that corresponds to the classical partition of the set of edge subsets into boolean intervals);

- the enumeration of orientation-activities for directed graphs;

- its refinement into a four variable expression in terms of subset orientation-activities (that corresponds to the partition of the set of orientations into active partition reversal classes);

- the convolution formula for the Tutte polynomial (that does not need the graph to be ordered);

- and an expression of the Tutte polynomial using only beta invariants of minors (that refines the above expressions).

I will mention that these expressions are all interrelated by the canonical active bijection between spanning trees and orientations, subject of a long-term joint work with Michel Las Vergnas.

05 janvier 2017
François Dross ()
Partition of sparse graphs into independent sets, forests and forests of bounded degree

As a generalization of proper colouring, we study vertex partitions of graphs into some graphs with particular properties, in particular independent sets, forests and forests with bounded degree. Proper colourings correspond to partitions into independent sets.

We will see some sufficient conditions for sparse graphs to admit such partitions. In particular, every planar graph of girth at least 4 admits a partition into a forest and a forest of maximum degree at most 5, and every planar graph of girth at least 7, 8 and 10 admits a partition into an independent set and a forest of maximum degree at most 5, 3 and 2 respectively.

15 décembre 2016
Marthe Bonamy (CNRS/ LABRI, Bordeaux)
Tight lower bounds for the complexity of multicoloring

In the multicoloring problem, also known as (a:b) or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the b=1 case) is equivalent to finding a homomorphism to the Kneser graph with parameters a and b. It is tightly connected with the fractional chromatic number, and has multiple applications within computer science.

We study the complexity of determining whether a graph has an (a:b)-coloring. Nederlof showed in 2008 a $(b+1)^n n^{O(1)}$-time algorithm for (a:b)-coloring. Our main result is that this is essentially optimal: there is no algorithm with running time $2^{o(log b)⋅n}$ unless the ETH fails. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström (1965), which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we also prove that the existing algorithms for the r-monomial detection problem are optimal under ETH.

This is joint work with Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała and Marcin Wrochna (University of Warsaw).

08 décembre 2016
Dimitrios Thilikos (CNRS, Lirmm, Montpellier / University of Athens)
Cutwidth: obstructions and algorithmic aspects

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k.

We prove that every minimal immersion obstruction for cutwidth at most k has size at most $2^{O(k^3 log k)}$. For our proof, we introduce the concept of a lean ordering that can be seen as the analogue of lean decompositions defined by Thomas in [A Menger-like property of tree-width: The finite case, J. Comb. Theory, Ser. B, 48(1):67–76, 1990] for the case of treewidth. As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $2^{O(k^2 log k)} · n$, where k is the optimum width and n is the number of vertices. While being slower by a log k-factor in the exponent than the fastest known algorithm, given by Thilikos, Bodlaender, and Serna in [Cutwidth I: A linear time fixed parameter algorithm, J. Algorithms, 56(1):1–24, 2005] and [Cutwidth II: Algorithms for partial w-trees of bounded degree, J. Algorithms, 56(1):25–49, 2005], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

Joined work with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, and Marcin Wrochna

03 novembre 2016
Mark Jones (Lirmm)
On the consistency of orthology relationships Transparents de l'exposé

Orthology relations between genes are an important part of comparaitve genomics, and a plethora of methods have been designed to infer these relations.
One particular property that must be maintained in orthology relations is consistency with the (possibly unknown) evolutionary history of the corresponding species.
Enforcing this property can be viewed as a problem of "embedding" one rooted tree within another.

We give the first polynomial algorithm to decide whether a partial set C of orthology/paralogy relations is consistent, even when the species tree is unknown. We also investigate a biologically meaningful optimization version of these problems, in which we wish to minimize the number of duplication events; unfortunately, we show that all these optimization problems are NP-hard and are unlikely to have good polynomial time approximation algorithms.

06 octobre 2016
Marin Bougeret (Lirmm)
Tutoriel : comment obtenir des résultats d'inapproximabilité pour son problème d'optimisation favori (ou plutôt, comment ignorer les nombreux outils de la théorie structurelle de l'approximation). Transparents de l'exposé

Dans cet exposé on fait un tour d'horizon rapide sur les outils existants pour prouver des résultats d'inapproximabilité. On a d'un côté les gap réductions, l'outil "idéal" puisque sa définition est très naturelle et qu'il permet d'obtenir des résultats forts. En effet, les nombreux résultats existants fournissent un large catalogue de problèmes pour lesquels
des résultats optimaux d'inapproximabilité sont connus. On peut alors souvent réutiliser ces résultats (en écrivant des gaps réductions depuis ces problèmes), et déduire ainsi des résultats d'inapproximabilité forts pour son problème cible. Nous ne parlerons donc *pas* des gaps réductions,
puisque la littérature correspondante est abondante et facile à appréhender.

D'un autre côté on trouve les "approximation preserving reductions". La difficulté est que derrière cette expression se cache un ensemble important de réductions (strict, S, L, E, A, AP, PTAS ..), et qu'il est donc difficile à première vue de choisir quelle réduction utiliser (en plus du problème source à choisir!). Cependant, il se trouve que certaines de ces réductions ont été introduites dans le cadre de la complexité structurelle, c'est à dire pour montrer qu'un problème, parfois artificiellement construit, est complet pour une certaine classe. Ainsi, en pratique (typiquement lorsque l'on cherche à montrer qu'un problème n'admet pas de PTAS), il *semble* que beaucoup de ces réductions ne soient pas utilisées, et que l'on cherche simplement à construire une réduction vérifiant une certaine condition suffisante plus naturelle que les définitions des réductions précédentes.

Nous parlerons de ces conditions suffisantes, et illustrerons à travers les preuves (simples) des résultats suivants :
- Vertex Cover n'admet pas de PTAS sur les graphes de degré maximum 3 (à moins que P=NP)
- MAX CUT n'admet pas de PTAS (à moins que P=NP)
- MAX 3SAT(B) (où chaque variable n'apparaît que dans au plus $B$ clauses) n'admet pas de PTAS (à moins que P=NP)

Nb : cet exposé n'est pas un exposé de recherche, et le niveau technique se veut faible.
Durée prévue : entre 30 et 45 min

29 septembre 2016
Lucia Penso ()
Geodetic convexity parameters for graphs with few short induced paths

We study parameters of geodetic convexity for graph classes defined by restrictions concerning short induced paths. We show that computing the geodetic hull number of a given $P_9$-free graph is NP-hard. Similarly, we show that computing the geodetic interval number of a given $P_5$-free graph is NP-hard. On the positive side, we identify several graph classes for which the geodetic hull number can be computed efficiently.

22 septembre 2016
Dieter Rautenbach (Ulm University, Allemagne)
Zero forcing Transparents de l'exposé

A set $Z$ of vertices of a graph $G$ is a zero forcing set of $G$ if
initially labeling all vertices in $Z$ with $1$ and all remaining vertices of $G$ with $0$, and then, iteratively and as long as possible, changing the label of some vertex $u$ from $0$ to $1$ if $u$ is the only neighbor with label $0$ of some vertex with label $1$, results in the entire vertex set of $G$.

The zero forcing number $Z(G)$, defined as the minimum order of a zero forcing set of $G$, was proposed as an upper bound of the corank of matrices associated with $G$, and was also considered in connection with quantum physics and logic circuits.

In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. We discuss such bounds and some of the corresponding extremal graphs.

Joint work with M. Gentner, L.D. Penso, and U.S. Souza.

15 septembre 2016
Rémi de Joannis de Verclos (Grenoble INP)
Easily testable properties of dense graphs

A graph of size $n$ is $\epsilon$-far from having a property P if one
have to add or delete at least $\epsilon n^2$ edges of G to have a graph
satisfying P. A graph property P is testable if for every $\epsilon$ there is a
constant $m(\epsilon)$ such that it is possible to distinguish (with one-sided
error) between graphs of P and graphs that are $\epsilon$-far of P with an algorithm that examines only a random induced subgraph of size $m(\epsilon)$ (which does not depend on the size
of the graph). It has been proven that every hereditary property is
testable but the query complexity $m(\epsilon)$ needed for this prove is an
exponential tower in $\frac{1}{\epsilon}$.
Following a work of Alon and Fox, we seek to classify graph classes for
which this query complexity $m(\epsilon)$ is a polynomial in $\frac{1}{\epsilon}$, which are called ”easily testable". We prove that the class of interval graphs and some subclasses of intervals graphs are easily testable.

01 septembre 2016
Jorgen Bang-Jensen (IMADA, University of Southern Denmark, Odense, Denmark)
Disjoint paths in tournaments and semicomplete digraphs

A digraph is semicomplete if it has no pair of non-adjacent vertices.
A tournament is a semicomplete digraph with no directed 2-cycles.
Tournaments form the most well studied class of directed graphs and a
lot is known about their structure, ranging from very basic things you can
teach a year student to extremely complicated things that take 100
pages or more to prove. I will survey some important results on connec-
tivity and give the main details of a recent proof, due to Pokrovskiy, that
every 452k-strong tournament T is k linked, that is, for every choice of 2k
vertices {x 1 , x 2 , . . . , x k , y 1 , y 2 , . . . , y k } there exist disjoint paths P 1 , P 2 , . . . , P k
in T so that P i is from x i to y i . Pokrovskiys beautiful proof of this result
uses a very nice structural lemma which applies to all tournaments. If
there is time, I will also say something more about the relation between
semicomplete digraphs and tournaments.

02 juin 2016
Ilda Perez Fernandez da Silva (Faculdade de Ciencias, Université de Lisbonne, Portugal)
Shannon switching game and directed variants

The “classical” Shannon switching game is a combinatorial game invented by C. Shannon in the 1950’s. The game was completely solved by A. Lehman, shortly after, in what is considered the first application of matroid theory. In the middle 1980’s Y. O. Hamidoune and M. Las Vergnas studied and solved directed versions of the game for graphs considering their generalization to oriented matroids. Recently with some colleagues and students of Informatics we made some proptotypes of computational implementations of the games. We will do a brief review of the main results and conjectures concerning the directed case.

A. P. Cláudio, S. Fonseca, L. Sequeira, I.P. Silva, Shannon switching
Game and directed variants, in Bourguignon, J.-P., Jeltsch, R., Pinto,
A.A., Viana, M. (Eds.) Dynamics, Games and Science II, CIM Series
in Mathematical Science 1, Springer 2015, 187-199.

26 mai 2016
Didem Gözüpek (Computer Engineering Department, Gebze Tehcnical University, Istanbul, Turkey)
Recent Results on Equimatchable Graphs

A graph is equimatchable if all of its maximal matchings have the same size. In this talk, I will present some recent results on equimatchable graphs such as forbidden subgraphs, stable equimatchable graphs, and the characterization of claw-free equimatchable graphs. I will then discuss about some new research directions.

12 mai 2016
Pas de séminaire (école CIRM) ()


28 avril 2016
Bastien Cazaux (Équipe MAB, LIRMM, Montpellier)
The Superstring Graph

Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. Building on recent theoretical work, I will present you a linear time algorithm for solving SCCS based on a Eulerian graph (the Superstring Graph) that captures all greedy solutions in linear space.

14 avril 2016
Jean-Florent Raymond (LIRMM (Montpellier, France) and University of Warsaw (Poland))
Packing and covering immersion models of planar subcubic graphs

A graph H is an immersion of a graph G if H can be obtained by lifting incident edges of some subgraph of G. We prove that there is a polynomial function f:N×N→N, such that if H is a connected planar subcubic graph on h>0 edges, G is a graph, and k is a non-negative integer, then either G contains k vertex/edge-disjoint subgraphs, each containing H as an immersion, or G contains a set F of f(k,h) vertices/edges such that G∖F does not contain H as an immersion.

This is join work with Archontia Giannopoulou (University of Warsaw), O-joung Kwon (Hungarian Academy of Sciences) and Dimitrios M. Thilikos (LIRMM). A preprint is online: .

31 mars 2016
Julien Baste (Equipe AlGCo, LIRMM, UM, Montpellier)
The number of labeled graphs of bounded treewidth

Treewidth is undoubtedly one of the most fundamental parameters in modern graph theory and algorithms. Its theoretical importance is demonstrated by its crucial role in the proof of the Graph Minor theorem by Roberston and Seymour, while its algorithmic relevance is certified, for instance, by Courcelle's theorem.

In this talk we focus on couting the number of labeled graphs on $n$ vertices and treewidth $k$, which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. Using a construction that exploits the fact that a graph has treewidth at most $k$ if and only if it is a partial $k$-tree, we show that

$$\left(c \cdot \frac{k}{\log k} \cdot 2^k \cdot n\right)^n \cdot 2^{-k(k+1)/2} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-k(k+1)/2} \cdot k^{-k},$$

for some explicit constant $c > 0$. Our results also apply to graphs of pathwidth at most $k$.

Joint work with Marc Noy and Ignasi Sau.

24 mars 2016
Eunjung Kim (CNRS, LAMSADE, Université Paris Dauphine)
The “art of trellis decoding” is fixed-parameter tractable

Given n subspaces of a finite-dimensional vector space over a fixed finite field 𝔽, we wish to find a linear layout V1,V2,…,Vn of the subspaces such that dim((V1+V2+⋯+Vi)∩(Vi+1+⋯+Vn))≤k for all i, such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory and computing the path-width of an 𝔽-represented matroid in matroid theory.

We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over 𝔽. As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input 𝔽-represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously.

It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width, a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field 𝔽, there are finitely many forbidden 𝔽-representable minors for the class of matroids of path-width at most k. An algorithm by Hliněný (2006) can detect a minor in an input 𝔽-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

17 mars 2016
Guillaume Guégan (Equipe AlGCo, LIRMM, UM, Montpellier)
From tournaments to unifom oriented matroids and vice versa

Locally transitive tournaments (LTT) are reorientations of the transitive tournament. Despite being a simple class to describe, they have rich and deep combinatorics. Uniform oriented matroids (UOM) can be understood as collections of LTT. I will present a new characterization of LTT which has a deep impact on the theory of UOMs:
1) the creation of new and interesting invariants;
2) characterization of lambda-functions of UOM (generalizing scores of tournaments).

10 mars 2016
Pas de séminaire (JCALMs) ()


25 février 2016
Matthieu Rosenfeld (MC2, LIP, ENS de Lyon)
Every long enough binary pattern is abelian 2-avoidable

We say that two words u and v are abelian equivalent if they have the same number of occurrences of each letter (i.e., they are permutations or anagrams). I will define what it means to avoid a pattern in the abelian sense. The interest in this topic is due to Erdös asking whether the pattern AA can be avoided in the abelian sense by an infinite words over 4 letters (the answer is yes). We obtain that every binary pattern of size at least 16 can be avoided by an infinite binary word.

18 février 2016
Ararat Harutyunyan (CIMI, Mathematical Institute, University of Toulouse III)
A proof of a conjecture of Barat and Thomassen

The Barat-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant k such that every k-edge-connected graph with size divisible by m can be edge-partitioned into copies of T . The conjecture has been verified when T is a path or when T has diameter at most 4. In the talk, I will sketch a recent proof of the conjecture.

This is joint work with J. Bensmail, T.-N. Le, M. Merker and S. Thomassé.

11 février 2016
Florian Barbero (Equipe AlGCo, LIRMM, Montpellier)
Cutwidth in Semi-Complete Digraphs

(English Below)

En collaboration avec Michal Pilipczuk (MIMUW, Warsaw).

Un digraphe $D = (V,E)$ est dit \emph{semi-complet} s'il est simple (pas de self-loop, pas de multi-edge) et que pour tous sommets $u,v \in V$ différents, l'arc $(u,v)$ ou l'arc $(v,u)$ est présent dans $E$. De plus, $D$ est un \emph{tournoi} si pour tous sommets $u,v \in V$ différents $(u,v)$ et $(v,u)$ ne sont pas simultanément présents. Récemment, Chudnovsky, Fradkin et Seymour ont montré que la relation d'immersion restrainte aux digraphes semi-complets était WQO en utilisant la mesure de largeur associée, appellée \emph{Cutwidth}. Ces notions ont ainsi trouvé un regain d'intérêt.

Durant ce séminaire, nous nous intéresserons à la cutwidth, définie de la manière suivante. Etant donné un digraphe $D$, un ordre $\pi$ sur les sommets de $D$ et une position $i \in [n]$, la $i$-ème coupe selon $\pi$ de $D$ est l'ensemble d'arcs de retour $D(\pi,i) = \{(v,u) \in E : u \in \pi[i], v \in V \setminus \pi[i]$, avec $\pi[i]$ représentant les $i$ premiers sommets de $\pi$. La cutwidth de $\pi$ est $ctw(D,\pi) = \max_{i \in [n]} D(\pi,i)$ et la cutwidth de $D$ est $ctw(D) = \min_{\pi} ctw(D,\pi)$.

Comme pour de nombreuses mesures de largeur, calculer la cutwidth est NP-Difficile dans le cas général. Nous prouverons que cela reste vrai lorsqu'on se restreint aux semi-complets mais qu'il est possible de calculer la cutwidth d'un tournoi en temps polynomial. A partir de ces résultats, nous montrerons comment approximer la cutwidth d'un semi-complet (de façon non linéaire toutefois) ou comment construire des petits tournois de cutwidth donnée. Nous montrerons aussi que tout tournoi contient un sous-tournoi induit de même cutwidth $c$ et de taille au plus linéaire en $c$. Nous étudierons également des variantes de {\sc Feedback Vertex/Edge Deletion}, à savoir {\sc Cutwidth Vertex Deletion} et {\sc Cutwidth Arc Reversal} (dans le cas restreint des semi-complets).

With Michal Pilipczuk (MIMUW, Warsaw).

A digraph $D = (V,E)$ is \emph{semi-complete} if it is simple (no self-loop, no multi-edge), and that, for all different vertices $u,v \in V$, the arc $(u,v)$or the arc $(v,u)$ is present in $E$. Moreover, $D$ is a \emph{tournament} if for all different vertices $u,v \in V$, $(u,v)$ and $(v,u)$ cannot be simultaneously present. Recently, Chudnovsky, Fradkin and Seymour proved that the immersion relation restricted to semi-complete digraphs is WQO, using the associated width measure called \emph{Cutwidth}. Hence, these notions deserve to be studied.

During this seminar, we will focus on cutwidth, defined as follows. Given a digraph $D$, an ordering $\pi$ of the vertices of $D$ and a position $i \in [n]$, the cut at position $i$ of $D$ using $\pi$ is the set of feedback arcs $D(\pi,i) = \{(v,u) \in E : u \in \pi[i], v \in V \setminus \pi[i]$, with $\pi[i]$ being the first $i$ vertices of $\pi$. The cutwidth of $\pi$ is $ctw(D,\pi) = \max_{i \in [n]} D(\pi,i)$ and the cutwidth of $D$ is $ctw(D) = \min_{\pi} ctw(D,\pi)$.

As for many width measures, computing the cutwidth is NP-Hard in general. We will prove it remains true even in the semi-complete case, but that computing the cutwidth of a tournament is polynomial. From these results, we will show how to approximate the cutwidth of a semi-complete digraph (in a non-linear manner, however), or how to construct small tournaments with a fixed cutwidth. We will also show that any tournament contains a sub-tournament with same cutwidth $c$ and size at most linear in $c$. Finally, we will study some generalization of {\sc Feedback Vertex/Edge Deletion}, called {\sc Cutwidth Vertex Deletion} and {\sc Cutwidth Arc Reversal} (restricted to semi-complete digraph).

28 janvier 2016
Aurelie Lagoutte (ENS Lyon)
Coloring perfect graphs with bounded clique number Transparents de l'exposé

Perfect graphs are graphs for which the chromatic number matches the trivial lower bound consisting in the clique number (and the same holds for every induced subgraph). After the long study that led to the Strong Perfect Graph Theorem, the main open question concerning them is about finding an optimal coloring with a combinatorial algorithm.
Indeed, deciding if the chromatic number of a graph is at most k is NP-complete in general, and even if k=3. A famous result of Lovasz, Grötchel and Schrijver provides a polynomial-time algorithm that optimally colors any perfect graph, however this algorithm uses the ellipsoid method which makes it unpractical and not combinatorial.
We design a purely combinatorial algorithm that, given in input a perfect graph, outputs an optimal coloring in time O(n^f) where f is quadratic in the clique number omega(G).

This is joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.

21 janvier 2016
Pascal Ochem (CNRS, LIRMM, Montpellier)
Partitioning into disjoint cliques and a triangle-free graph

We consider the complexity of deciding whether a graph admits a vertex partition into two parts R and B such that R is K_3-free and B is P_3-free. We show that the problem is NP-complete for 9 small graph classes, where "small" means that if we take the intersection of any two classes among these nine, the problem becomes trivial because the answer is always yes.

Joint work with Marin Bougeret.

14 janvier 2016
Emeric Gioan (CNRS, LIRMM, Montpellier)
A Survey on The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids

En preambule de l'abstract general, je previens qu'il s'agira d'un expose assez vaste et plus long que d'habitude (1h30), et qu'il y aura deux brefs passage type groupe de travail pour poser les questions suivantes aux algorithmiciens de l'equipe, propices pour approfondissements dans le cas particulier des graphes (cf. details dans courriel et article envoyes a l'equipe en octobre) :

1 - On s'interesse aux graphes bipolaires et on en definit une coupe optimale. Combien coute de trouver une coupe orientee de poids minimum, pour une fonction poids sur les aretes positive ou nulle ? Combien coute de trouver une coupe de poids minimum, orientee sauf pour certaines aretes d'un arbre couvrant, pour un poids qui est positif/negatif selon l'orientation de ces aretes ? (je sais repondre polynomialement mais en passant par la programmation lineaire, j'aimerais des solutions en termes de graphes)

2 - On introduit une decomposition des graphes orientes en graphes bipolaires (cycliques ou acycliques) dont les nombres sont des parametres combinatoires classiques. Cela pourrait-il etre utilise en complexite parametree ? Verriez-vous par exemple un probleme facile sur les graphes bipolaires, et resoluble en decomposant un graphe acyclique (ou fortement connexe) en de tels mineurs ?


The active bijection maps any directed graph, resp. signed hyperplane arrangement or oriented matroid, defined on a linearly ordered edge set, resp. ground set, onto one of its spanning trees, resp. bases.

It relates all spanning trees to all orientations of a graph, all bases to all reorientations of an hyperplane arrangement or, more generally, an oriented matroid. It preserves activities: for bases in the sense of Tutte, for orientations in the sense of Las Vergnas, yielding a bijective interpretation of the equality of two expressions of the Tutte polynomial. It preserves also some active partitions associated with orientations and bases. It can be mathematically defined in a short way, and can be built, characterized, particularized, or refined in several ways.

Notably, we get a bijection between bounded regions (bipolar orientations in the case of a graph) and bases with internal activity one and external activity zero, which can be seen as an advanced refinement of real (pseudo)linear programming. We get a bijection between classes of reorientations and bases, using a decomposition into bounded regions of minors of the primal and the dual, which also has a counterpart for decomposing matroid bases, and yields an expression of the Tutte polynomial using only beta invariants of minors.

We also get activity preserving bijections between all reorientations and all subsets (related to a four-variable expression of the Tutte polynomial), between regions and no-broken-circuit subsets (acyclic case), between reorientations with fixed orientations for smallest elements of positive circuits/cocircuits (directed cycles/cocycles) and bases (spanning trees), between increasing trees and permutations (complete graph case), etcetera.

It is the subject of a series of papers, joint with Michel Las Vergnas.

07 janvier 2016
Mark Jones (Equipe AlGCo (LIRMM, Montpellier))
Parameterized Complexity of the Mixed Chinese Postman Problem

In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph G (G may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP was known to be polynomial-time solveable on graphs containing only edges or only arcs. It was known to be fixed-parameter tractable parameterized by the number of edges using a simple argument. In this talk, I'll show that the MCPP parameterized by the number of arcs is also fixed-parameter tractable. The proof uses a well-known result of Marx, O'Sullivan and Razgon on the treewidth of torso graphs with respect to small separators. We obtain a small cut analog of this result, and use it to construct a tree decomposition which, despite not having bounded width, has other properties allowing us to design a fixed-parameter algorithm. I will also discuss structural parameterizations of the MCPP, including treewidth and treedepth.

17 décembre 2015
Jean-Florent Raymond (LIRMM (Montpellier, France) and University of Warsaw (Poland))
Mineurs de cliques dans les graphes de grande maille

En 2003, Kühn et Osthus ont prouvé que tout graphe sans petit sommet contient comme mineur une clique de taille exponentiellement grande par rapport à sa maille (càd la taille d'un plus petit cycle).

En étendant la notion de maille, nous donnons des conditions alternatives pour qu'un graphe contienne une grande clique comme mineur. Pour tout graphe H, la H-maille d'un graphe G et la taille d'un plus petit sous-graphe de G qui se contracte en H. Cette notion généralise celle de maille qui correspond à la θ_2-maille, où θ_r est le graphe à 2 sommets et r arêtes.

Nous montrons que pour tout entier r, les graphes de grand degré minimum contiennent comme mineur des cliques dont l'ordre est une fonction exponentielle de leur θ_r-maille. Ce résultat étend celui de Kühn et Osthus à la notion de H-maille. Nous donnons également des critères de connectivité garantissant la présence d'une telle clique.

Ces résultats peuvent être utilisés par exemple pour obtenir des théorèmes de type Erdős-Pósa, ou pour borner la tree-width des graphes excluant certains mineurs.

Travail commun avec Dimitris Chatzidimitriou (National and Kapodistrian University of Athens), Ignasi Sau (LIRMM) et Dimitrios M. Thilikos (LIRMM et National and Kapodistrian University of Athens).

03 décembre 2015
Ilkyoo Choi (KAIST, Daejeon, Korea)
Obtaining chi-bounded families by forbidding substructures

The clique number is a trivial lower bound for the chromatic number of a graph. Since Erd\H{o}s showed the existence of graphs with arbitrarily high chromatic number and arbitrarily high girth (so clique number is 2), in general, the chromatic number of a graph cannot be upper bounded by a function of its clique number. A class of graphs is said to be $\chi$-bounded if such a function exists.

Vertex-minor and pivot-minors are graph containment properties such as (induced) subgraphs, subdivisions, and minors. Geelen conjectured that for any fixed graph $H$, the class of graphs with no $H$-vertex-minor is $\chi$-bounded. This conjecture was known to be true only for one graph (proved by Dvo\v{r}\'ak and Kr\'al), but recently Chudnovsky, Scott, and Seymour proved it for any cycle. We add another class of graphs for which Geelen's Conjecture is true, namely, fan graphs.

We also ask the following question of whether Geelen's Conjecture can be generalized to pivot-minors: for any fixed graph $H$, are the class of graphs with no $H$-pivot-minor $\chi$-bounded? We give some positive evidence to this question by proving that it is true for all cycles, which is a strengthening of the aforementioned result by Chudnovsky, Scott, and Seymour. This result can also be viewed as a partial result of the last open conjecture among the three conjectures made by Gy\'arf\'as' in 1985.

26 novembre 2015
Florian Barbero (Projet AlGCo, LIRMM)
Parameterized and Optimization algorithm for the c-Load Coloring problem

For a positive integer $c$, let $[c] = \{1, \ldots , c\}$. The $c$-Load Coloring problem is as follows: given a graph $G=(V,E)$ and an integer $k$ as parameter, decide whether there exists a coloring $q : V \to [c]$ such that for every $i$ in $[c]$, there are $k$ edges with both endvertices colored $i$ in $q$.

This problem was studied when $c = 2$ inter alia for its application in broadcast WDM communication networks. It was known that 2-Load Coloring is NP-complete and has a constant ratio approximation. For this sub-case, we had a kernel with at most $7k$ vertices and a dynamic programming algorithm simple-exponential in treewidth, thus 2-Load Coloring is FPT simple-exponential.

During my internship in Royal Holloway, I generalized and improved all these results by obtaining a linear-vertex and linear-edge kernel for c-Load Coloring, $c > 1$ being fixed. To prove this kernel, I described a new obstacle I called overload, and showed how to use the related reduction rules in polynomial time. These results imply that $c$-Load Coloring is FPT simple-exponential and the optimization version of $c$-Load Coloring (where $k$ is to be maximized) has an approximation algorithm with a constant ratio. It is even possible that this problem admits a sub-exponential parametrized algorithm. I proved this complexity for graphs of bounded genus, chordal graphs and $H$-free families, where $H$ is a constant forbidden minor. The team of my internship supervisor and I published a conference paper in the International Symposium on Parameterized and Exact Computation (IPEC 2015).

19 novembre 2015
Pas de séminaire (JCALMs à Marseille) ()


12 novembre 2015
Spencer Backman (Department of Computer Science, University of Rome "La Sapienza", Italy)
Graph Fourientations and the Tutte Polynomial

A fourientation of a graph is a choice for each edge whether to orient that edge in either direction, leave it unoriented, or biorient it. Fourientations can naturally be viewed as a mixture of graph orientations and subgraphs where unoriented and bioriented edges play the roles of absent and present edges, respectively. The Tutte polynomial is the most general bivariate polynomial associated to a graph which can be defined using the deletion and contraction of edges. I will describe joint work with Sam Hopkins where we investigate properties of cuts and cycles in fourientations which determine classes of fourientations which are enumerated by Tutte polynomial evaluations. Time permitting, I will illustrate how several of these classes relate to algebraic, combinatorial, and geometric topics such as Riemann-Roch theory for graphs, bigraphical arrangements, Lawrence ideals, zonotopal algebras, and the reliability polynomial.

05 novembre 2015
Didem Gözüpek (Computer Engineering Department of Gebze Technical University, Turkey)
Equimatchable graphs are C_{2k+1}-free for k>=4

A graph is equimatchable if all of its maximal matchings have the same size. Equimatchable graphs are extensively studied in the literature mainly from structural point of view. In this talk I will talk about, to the best of our knowledge, the fi rst family of forbidden subgraphs of equimatchable graphs. Since equimatchable graphs are not hereditary by defi nition, this task of finding forbidden subgraphs requires the use of structural results from previous works.

29 octobre 2015
Pas de séminaire (vacances) (CNRS, LIRMM)


22 octobre 2015
Pas de séminaire (AG) ()


15 octobre 2015
Pas de séminaire (GROW à Aussois) ()


08 octobre 2015
Dieter Rautenbach (Institut fur Optimierung und Operations Research - Universitat Ulm - Germany)
Graphs in which some or every maximum matching is uniquely restricted

A matching $M$ in a graph $G$ is uniquely restricted if there is no matching $M'$ in $G$ that is distinct from $M$ but covers the same vertices as $M$. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.

Joint work with Lucia D. Penso and Uéverton dos Santos Souza.

01 octobre 2015
Stéphane David-Grignot (LIRMM)
Open-Membership Consensus Protocol

I will present David Mazières’ “Stellar Consensus Protocol”, a decentralized agreement process. Robustness from this approach to consensus, stems from quorum slices, individual trust decisions made by each node, that together determine system-level quorums. This protocol is a Byzantine agreement which makes no assumptions about the rational behavior of attackers. Unlike prior Byzantine agreement models, which presuppose a unanimously accepted membership list, this protocol enables any node to freely join and promotes organic network growth. Study perspectives will be outlined concerning the quorum slices function which makes an interesting graph structure that is prone for an optimized implementation. A potential application of the protocol as the base for a crypto-currency will also be introduced.

24 septembre 2015
François Dross (Equipe AlGCo, LIRMM, Montpellier)
Décomposition fractionnelle en triangles de graphes presque complets

Une décomposition (entière) d'un graphe en triangles est une partition de ses arêtes en triangles. Une décomposition fractionnelle d'un graphe en triangles est une assignation d'un poids positif à chaque triangle du graphe tel que, pour toute arête e, la somme des poids des triangles contenant e est égale à 1. On montre que tout graphe à n sommets de degré minimum au moins 0.9n a une décomposition fractionnelle en triangles.

La preuve se fait en partant d'une affectation simple de poids aux triangles, et en l'adaptant pour obtenir une décomposition fractionnelle en triangles.

17 septembre 2015
Éric Fusy (LIX, France)
Bijections pour cartes d-angulées

Nous présentons une méthode bijective générale pour les cartes planaires, basée sur certaines orientations, appliquée ici à deux familles de cartes $d$-angulées pour $d \geq 3$: les $d$-angulations de maille $d$ (tous les cycles ont longueur au moins $d$), et les dissections irréductibles $d$-angulées (où les seuls cycles de longueur $\leq d$ sont les contours de faces internes).

Travail en commun avec Olivier Bernardi.

10 septembre 2015
Marin Bougeret (LIRMM, équipe AlGCo, Université de Montpellier)
On independent set on B1-EPG graphs

In this talk we consider the Maximum Independent Set problem (MIS) on $B_1$-EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) is the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class $B_k$-EPG denotes EPG-graphs where every path has at most $k$ bends. It was already known that MIS on $B_1$-EPG graphs is NP-complete and admits a $4$-approximation.

In this talk we consider the approximability and the fixed parameter tractability of MIS on $B_1$-EPG. We will discuss the conditions guaranteeing the existence of a PTAS, and we will show that MIS is FPT in the standard parameterization on $B_1$-EPG restricted to only three shapes of path. As we know that MIS is W1-hard on $B_2$-EPG, the main open question is the FPT status on general $B_1$-EPG.

Travail en commun avec Stéphane Bessy, Daniel Gonçalves et Christophe Paul.

03 septembre 2015
Dimitrios M. Thilikos (CNRS, LIRMM, équipe AlGCo, Montpellier)
Bidimensionality Theory: a Retrospective

We provide an exposition of the main results of the theory of bidimensionality in parameterized algorithm design. This theory applies to graph problems that are bidimensional in the sense that (i) their solution value is not increasing when we take minors or contractions of the input graph and (ii) their solution value for the (triangulated) $(k\times k)$-grid graph grows as a quadratic function of $k$. Under certain additional conditions, mainly of logical and combinatorial nature, such problems admit sub-exponential parameterized algorithms and linear kernels when their inputs are restricted to certain topologically defined graph classes. We provide all formal definitions and concepts in order to present these results in a rigorous way and in their latest update.

25 juin 2015
Julien Baste (Equipe AlGCo, LIRMM, UM, Montpellier)
Parameterized complexity dichotomy for (r,l)-Vertex Deletion

For two integers $r, \ell \geq 0$, a graph $G = (V, E)$ is an $(r,\ell)$-graph if $V$ can be partitioned into $r$ independent sets and $\ell$ cliques. In the parameterized $(r,\ell)$-Vertex Deletion problem, given a graph $G$ and an integer $k$, one has to decide whether at most $k$ vertices can be removed from $G$ to obtain an $(r,\ell)$-graph. This problem is NP-hard if $r+\ell \geq 1$ and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of $(r,\ell)$-Vertex Deletion was known for all values of $(r,\ell)$ except for $(2,1)$, $(1,2)$, and $(2,2)$. We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of $k$. We consider as well the version of $(r,\ell)$-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

This is joint work with Luerbio Faria, Sulamita Klein, and Ignasi Sau.

18 juin 2015
Nicolas Bonichon (LaBRI , Université Bordeaux-1, France)
Upper and Lower Bounds for Competitive Online Routing on Delaunay Triangulations

Consider a weighted graph G where vertices are points in the plane and edges are line segments. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a competitive ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c times the length of the shortest path from s to t in G. If the length of the path is at most c times the Euclidean distance from s to t, we say that the routing algorithm on G has a routing ratio of c.We present an online routing algorithm on the Delaunay triangulation with competitive and routing ratios of 5.90. This improves upon the best known algorithm that has competitive and routing ratio 15.48. The algorithm is a generalization of the deterministic 1-local routing algorithm by Chew on the L1-Delaunay triangulation. When a message follows the routing path produced by our algorithm, its header need only contain the coordinates of s and t. This is an improvement over the currently known competitive routing algorithms on the Delaunay triangulation, for which the header of a message must additionally contain partial sums of distances along the routing path.We also show that the routing ratio of any deterministic k-local algorithm is at least 1.70 for the Delaunay triangulation and 2.70 for the L1-Delaunay triangulation. In the case of the L1-Delaunay triangulation, this implies that even though there exists a path between two points x and y whose length is at most 2.61|[xy]| (where |[xy]| denotes the length of the line segment [xy]), it is not always possible to route a message along a path of length less than 2.70|[xy]|. From these bounds on the routing ratio, we derive lower bounds on the competitive ratio of 1.23 for Delaunay triangulations and 1.12 for L1-Delaunay triangulations.

Joint work with Prosenjit Bose, Jean-Lou De Carufel, Ljubomir Perković, and André Van Renssen.

11 juin 2015
Ignasi Sau (CNRS, LIRMM, équipe AlGCo, Montpellier)
On the complexity of computing the k-restricted edge-connectivity of a graph

The $k$-restricted edge-connectivity of a graph $G$, denoted by $\lambda_k(G)$, is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least $k$ vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing $\lambda_k(G)$. Very recently, in the parameterized complexity community the notion of good edge separation of a graph has been defined, which happens to be essentially the same as the $k$-restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP-hardness and W[1]-hardness results, as well as FPT-algorithms.

This is joint work with Luis P. Montejano.

28 mai 2015
Luis Pedro Montejano (Département de Mathématiques, Université de Montpellier 2, Montpellier, France)
Transversals to the convex hulls of all k-sets of discret substets of R^d

Let $k,d,\lambda$ be positive integers with $d\ge\lambda$. We investigate the following two questions. What is the maximum positive integer $n$ such that every set of $n$ points in $\mathbb{R}^d$ has a (kneser) transversal $(d-\lambda)$-plane intersecting the convex hulls of all $k$-sets ? What is the minimum positive integer $n$ such that every set of $n$ points in general position in $\mathbb{R}^d$ there is no (kneser) transversal $(d-\lambda)$-plane intersecting the convex hulls of all $k$-sets ? A transversal $(d-\lambda)$-Plane in $\mathbb{R}^d$ is an affine subspace of dimension $d-\lambda$. A kneser transversal $(d-\lambda)$-plane for a set of points $S$ in $\mathbb{R}^d$ is an affine subspace of dimension $d-\lambda$ that goes through $d-\lambda+1$ points of $S$. First question is related with Kneser hypergraph and its chromatic number (when $\lambda=1$, it is equivalent to Kneser's conjecture). We will see how answering first question could give improvements to this problem.

21 mai 2015
Dimitrios M. Thilikos (CNRS, LIRMM, AlGCo)
Linkages and cyclic linkages

The cyclability of a graph is the maximum integer $k$ for which every $k$ vertices lie on a cycle. The algorithmic version of the problem, given a graph $G$ and a non-negative integer $k,$ decide whether the cyclability of $G$ is at least $k,$ is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by $k,$ is W[1]-hard and that its does not admit a polynomial kernel on planar graphs, unless $NP\subseteq coNP/poly$. On the positive side, we give an FPT algorithm for planar graphs that runs in time $2^{2^{O(k^2\log k)}}\cdot n^2$. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. The algorithm is based on combinatorial results on linkages and cyclic linkages on planar graphs.

Joint work with Petr A. Golovach, Marcin Kamiński, and Spyridon Maniatis.

07 mai 2015
Valia Mitsou (Research Institute for Mathematical Sciences, Kyoto University, Japan)
The computational complexity of two card games with theoretical applications Transparents de l'exposé

The main theme of this talk is card games that can be naturally reformulated as well-known graph-theoretic problems. In particular, we will focus on two different games: the game of SET, and the game of UNO. The objective of the former is to form sets of cards that match in a certain sense, while in the latter players need to discard their cards following a matching rule (for more details regarding the rules of the two games please visit the following websites: official website of SET, wikihow: how to play UNO).

We will describe connections of the two games with a number of different problems such as Multidimensional Matching, Set Packing, Edge Dominating Set, and Hamiltonian Path. These connections will help us show algorithmic as well as hardness results for variations of both games in the classical and the parameterized sense. The connections described are two-fold as our results will, in several cases, imply progress for the state of the art of the corresponding graph-theoretic problems.

This talk will include results from two different publications: "The computational complexity of the game of SET", joint with Michael Lampis, LATIN 2014, and "Parameterized Edge Hamiltonicity", joint with Michael Lampis, Kazuhisa Makino, and Yushi UNO, WG 2014.

30 avril 2015
Morgan Chopin (Institut für Optimierung und Operations Research, Universität Ulm, Germany)
Complexité structurelle du problème du pompier

Dans cet exposé, nous allons nous intéresser au problème du pompier (firefighter) qui est défini de la manière suivante: initialement un sommet particulier d'un graphe non-orienté est brûlé. À chaque pas de temps, on applique successivement les deux étapes suivantes: 1) Protéger un sommet non-brûlé du graphe, i.e. il ne peut plus brûler par la suite; 2) Tous les sommets non-protégés et adjacents à un sommet brûlé sont brûlés. Le processus se termine lorsque plus aucun nouveau sommet ne peut brûler. Un sommet est alors considéré comme sauvé s'il n'est pas brûlé. L'objectif est de trouver une stratégie de protection telle que le nombre de sommets brûlés à la fin du processus est minimum. Nous considérons ici la version plus générale du problème qui permet de protéger b sommets par étape. Nous présenterons des résultats de complexité paramétrée de ce problème par rapport à des paramètres liés à la structure du graphe. En particulier, nous montrerons que la complexité du problème est directement liée à la largeur linéaire (pathwidth) et au degré maximum du graphe.

Résultats obtenus en collaboration avec Janka Chlebíková.

23 avril 2015
Edouard Bonnet (Institute for Computer Science and Control of the Hungarian Academy of Sciences, Budapest)
Super-polynomial time approximability of inapproximable problems

Most of the NP-hard problems are even hard to approximate within some super-constant ratio (Max Clique, Min Indepedent Dominating Set, Min Set Cover etc.). For each of these problems, from the known polytime $\rho(n)$-approximation to the best super-polynomial time exact algorithm, one can ask a continuum of question of the form: for $r < \rho(n)$, what is the best running time of an r-approximation algorithm? In 2013, Chalermsook, Laekhanukit, and Nanongkai answered the question for Max Independent Set/Max Clique, by showing that the previously known $r$-approximation in time $2^{n/r}$ was nearly optimal under standard complexity assumptions. However, for other problems there have been only some upper bounds (by Bourgeois et al. and Cygan et al.) without nearly matching lower bounds.

We start to fill this gap by showing that Min Independent Dominating Set, Max Induced Path/Tree/Forest, and Max Minimal Vertex Cover present about the same behavior as Max Independent Set in being $\rho(r)$-approximable in time $2^{n/r}$ but not with a significantly better time. We also present some upper bounds for Min Asymmetric TSP and Max Grundy Coloring. It is still unknown whether or not these two problems are polytime constant-approximable. We conclude with some words concerning Min Set Cover.

This is joint work with Michael Lampis and Vangelis Paschos.

09 avril 2015
Stéphane Bessy (UM2, LIRMM, AlGCo)
Antistrong digraphs

Pour d'obscures raisons, nous définissons la notion de graphe orienté
antistrong (par opposition à strong -fortement connexe-). Un graphe orienté
est antistrong si tout couple de points peut être relié par un parcours orienté alternant.
La (bonne) caractérisation d'un graphe antistrong est que son graphe biparti
d'incidence est connexe.
On s'est intéressé principalement à des questions algorithmiques autour
de cette notion. Certaines découlent facilement de la caractérisation précédente,
d'autres sont plus difficiles à établir. Des techniques matroïdales ont notamment
été utiles pour obtenir certains résultats.

Dans cet exposé, je motiverai et présenterai ces différents résultats. J'en profiterai pour
faire aussi le tour de quelques outils de matroïdes pour graphes qui, bien que pas
récents, m'ont enthousiasmé récemment...

Travail commun avec J. Bang-Jensen, B. Jackson et M. Kriessell.

02 avril 2015
Vincent Despré (GIPSA-lab, Grenoble, France)
Les différentes notions de simplicité, cas particulier du cycle de partage Transparents de l'exposé

On s'intéresse aux graphes plongés sur des surfaces. Dès qu'on considère une surface plus compliquée que le plan ou la sphère des problèmes topologiques apparaissent. Beaucoup de travaux on été réalisés dans un cadre purement mathématiques sur le sujet y compris des travaux de nature algorithmique. Cependant les algorithmes proposés ne sont pas réellement utilisables en général. Certaines notions comme la simplicité sont problématiques. Effectivement, on obtient beaucoup plus facilement une courbe simple (sans point double) sur la surface qu'un cycle simple (sans sommet répété) dans un graphe plongé. On s'intéressera en particulier à la recherche de cycles simples (au sens du graphe) qui permettent de découper la surface sous-jacente en 2 parties non-planaires i.e. les cycles de partage.

26 mars 2015
Mathieu Liedloff (LIFO, Université d'Orléans, France)
Minimal dominating sets on some graph classes: combinatorial upper bounds and enumeration

Given a graph $G=(V,E)$, a subset $D$ of vertices is a dominating set if each vertex is either in $D$ or has at least one neighbor in $D$. A dominating set is minimal if it contains no dominating set as a proper subset.

An interesting question is to determine the maximum number of minimal dominating sets in a graph. In this talk we provide upper bounds on this maximum number for various graph classes (split, cobipartite and interval graphs). These bounds are established via the running-time analysis of exponential-time algorithms which enumerates all the minimal dominating sets.

19 mars 2015
Gabriel Renault (LABRI, Bordeaux, France)
Misère Geography and Vertex NimG are pspace-hard Transparents de l'exposé

Geography and Vertex NimG are both games played on a graph. On their turn, a player moves a token along an arc and modifies the graph locally. In Geography, the player removes the vertex the token was on or the arc the token just slided along, depending on the variant. In Vertex NimG, the graph is weighted and the player decreases the weight of the vertex the token was on or the weight of the vertex the token just arrived on, depending of the variant. The game stops when a player cannot move. Under the misère convention, that player is considered the winner of the game. We see that these games are all pspace-hard in the general family of all graphs.

12 mars 2015
Julien Bensmail (LIP, ENS Lyon, France)
Strong edge-coloring of $(3,\Delta)$-bipartite graphs Transparents de l'exposé

An edge-coloring of a graph $G$ is strong if its every color class is an induced matching. The strong chromatic index of $G$, denoted $\chi'_s(G)$, is the least number of colors in a strong edge-coloring of $G$. Greedy coloring arguments show that $\chi'_s$ is bounded above by roughly $2\Delta^2$, where $\Delta$ denotes the maximum degree of an implicit graph, though this upper bound is not reached in general. A long-standing conjecture of Erdös and Nešetřil (1989) states that the right upper bound on the strong chromatic index should actually be roughly $1.25\Delta^2$, which would be tight as confirmed by a particular family of graphs with a lot of small cycles ($C_4$'s and $C_5$'s). Excluding small cycles (i.e. with length at most $5$) in a graph is expected to make the strong chromatic index be smaller, as confirmed notably by Mahdian (2000) for $C_4$-free graphs. This observation made Faudree, Gyárfás, Schelp and Tuza (1990) conjecture that the strong chromatic index of bipartite graphs (which have no $C_3$'s and $C_5$'s) should be bounded above by $\Delta^2$. In the continuity of previous results of Steger and Yu (1993) and Nakprasit (2008), we verify this conjecture for bipartite graphs whose one part is of maximum degree at most$3$.

This is a joint work with A. Lagoutte and P. Valicov.

05 mars 2015
Christophe Paul (CNRS, LIRMM, AlGCo)
Rankwidth vertex deletion

Le problème Rankwidth-c Vertex Deletion consiste à supprimer k sommets pour obtenir un graphe de ranwkdith au plus c, où c est une constante. Ce problème est non-uniforme FPT paramétré par k. La question posée est de savoir si ce problème peut être résolu en temps FPT simple exponentiel. Le cas c=1 est intéressant pour plusieurs raisons. Il correspond au problème Distance Hereditary Graphs Vertex Deletion et est l'analogue pour la treewidth au problème Feedback Vertex Set. Nous répondons positivement à la question et montrons l’existence d’un noyau polynomial pour les graphes de rankwidth linéaire 1.

Co-auteurs: M. Kanté (LIMOS), E.J. Kim (LAMSADE), O. Kwon (KAIST, Korea).

26 février 2015
Guilherme D. da Fonseca (Université de Monpellier 2, France)
Approximate Polytope Membership Queries Transparents de l'exposé : Fichier 1 Fichier 2

We consider an approximate version of a fundamental geometric search problem, polytope membership queries. Given a convex polytope P in d-dimensional space, presented as the intersection of halfspaces, the objective is to preprocess P so that, given a query point q, it is possible to determine efficiently whether q lies inside P subject to an allowed error ε. Previous solutions to this problem were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former yields minimum storage, the latter yields constant query time, and a space-time tradeoff can be obtained by interpolating between the two.

We present the first significant improvements to this tradeoff. For example, using the same storage as Dudley, we reduce the query time from O(1/ε^(d-1)/2) to O(1/ε^(d-1)/4) and, using a more involved analysis, to O(1/ε^(d-1)/8). Our approach is based on a very simple construction algorithm, whose analysis is surprisingly nontrivial. Both lower bounds and upper bounds on the performance of the algorithm are presented. For the same storage as Dudley, we present a lower bound of Ω(1/ε^(d-1)/18).

To establish the relevance of our results, we introduce a reduction from approximate nearest neighbor searching to approximate polytope membership queries. Remarkably, we show that our tradeoff provides significant improvements to the best known space-time tradeoffs for this very well studied problem.

This is joint work with Sunil Arya and David M. Mount.

12 février 2015
Tereza Klimošová (University of Warwick, U.K.)
Infinite dimensional finitely forcible graphon

Graphons are analytic objects associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible. We show that there exists a finitely forcible graphon such that the topological space of its typical vertices has infinite Lebesgue covering dimension, disproving the conjecture by Lovasz and Szegedy. The talk is based on joint work with Roman Glebov and Dan Král'.

05 février 2015
Pascal Ochem (CNRS, LIRMM, projet AlGCo)
Homomorphism of 2-edge-colored and 2-vertex-colored graphs

The CSP dichotomy conjecture is that every constraint satisfaction problem is polynomial or NP-complete. Feder and Vardi have shown that the CSP conjecture can be reduced to the case of digraph homomorphism. Hell and Nesetril settled the complexity of homomorphism to a graph G: it is polynomial if G is bipartite and NP-complete otherwise. We will show that the CSP conjecture can be reduced to the case of 2-edge-colored homomorphism and to the case of 2-vertex-colored homomorphism (also known as tropical homomorphism).

It is a joint work with Nazanin Movarraei.

29 janvier 2015
O-joung Kwon (KAIST, Daejeon, South Korea)
A fixed parameter tractable algorithm for linear rank-width using the obstruction set

We first give a brief introduction of rank-width and linear rank-width. Even though rank-width has been well developed by a series of papers, only few known algorithmic or structural properties are developed for linear rank-width until recently. We list some problems related to this area, and then focus on a fixed parameter tractable algorithm using the obstruction set for bounded linear rank-width. We mainly show that the number of pivot-minor obstructions for linear rank-width at most k is doubly exponential in O(k).

15 janvier 2015
Ignasi Sau (CNRS, LIRMM, projet AlGCo)
FPT algorithm for a generalized cut problem and some applications

In this talk we will sketch an FPT algorithm for a quite general cut problem on general graphs, which we call List Allocation. Our algorithm strongly uses the "edge contraction" technique introduced by Chitnis et al. [2012]. Besides being a natural cut problem by itself, the relevance of List Allocation is best demonstrated by the following algorithms, which we obtain by reducing in FPT time each corresponding problem to particular cases of List Allocation:

(1) An FPT algorithm for a generalization of Digraph Homomorphism, which we call Arc-Bounded List Digraph Homomorphism.
(2) An FPT algorithm for a graph partitioning problem, which we call Min-Max Graph Partitioning.
(3) An FPT 2-approximation algorithm for computing the "tree-cut width" of a graph, a graph invariant recently introduced by Wollan [2013] and that has proved of fundamental importance in the structure of graphs not admitting a fixed graph as an immersion.

If time permits, we will partially discuss the above applications of our main algorithm.

This is joint work with EunJung Kim, Sang-Il Oum, Christophe Paul, and Dimitrios M. Thilikos.

18 décembre 2014
Guillem Perarnau (School of Computer Science, McGill University, Montréal, Canada)
Edge-decompositions of graphs with maximum bounded degree

In this talk I will introduce two problems on edge-decompositions of graphs with bounded maximum degree. First, I will present a new approach to acyclic edge colorings of graphs with large girth. Using it, we obtain asymptotically tight results on a conjecture of Alon, Sudakov and Zaks. In the second part I will talk about the problem of partitioning the edges of a graph in different improper color classes with no monochromatic copy of a fixed graph. I will present an iterative embedding argument that allows us to transfer classical results from Extremal Graph Theory to bounded degree graphs. The common denominator of these two topics is the use of the so-called semirandom method. All the presented results are joint work with Cai, Reed and Watts (Part 1) and with Foucaud, Kang, Krivelevich and Reed (Part 2).

11 décembre 2014
Mickael Montassier (UM2, LIRMM, projet AlGCo)
3-paths with given degree sequence

In this talk, we present results on the existence of paths of length 3 with given degree sequence in sparse graphs.

Joint work with S. Jendrol, M. Macekova, and R. Sotak.

04 décembre 2014
Benjamin Lévêque (CNRS, LIRMM, projet AlGCo)
Structure of Schnyder labelings on orientable surfaces

We propose a simple generalization of Schnyder woods to higher genus. We give a necessary and sufficient condition for an orientation to corresponds to such a Schnyder wood and we study the relations between these orientations. Unfortunately we are not able to prove the existence of these Schnyder woods in general but a new proof for the toroidal case is derived from this study.

27 novembre 2014
Céline Scornavacca (CNRS, ISEM, Montpellier, France)
(Strict) compatibility of unrooted phylogenetic trees

A collection F of k unrooted phylogenetic trees on different leaf sets is said to be compatible if there exists a tree T such that each tree in F can be obtained from T by deleting leaves, suppressing degree-2 vertices, and by contracting edges. In the case of strict compatibility, the latter operation is not permitted.
The problem of determining if a set of unrooted trees is (strictly) compatible has been proved NP-hard in 1992. In this seminar, I will use Monadic Second Order (MSO) logic to prove that an f(k)·n algorithm for these problems exists, for some computable function f of k, proving that (strict) compatibility of unrooted phylogenetic trees is fixed-parameter tractable with respect to the number k of trees. Designing a practical FPT algorithm remains an open problem.
If time, I will give alternative, compact proofs of fixed parameter tractability for the computation of several well-known incongruency parameters in phylogenetics, ie the rSPR distance.

20 novembre 2014
Arnau Padrol (Institut für Mathematik, Freie Universität Berlin)
Realizations of neighborly, inscribable and egg-scribable polytopes

Delaunay triangulations in R^d are a central object in many areas of mathematics and computational geometry. However, little is known about which combinatorial types can appear as a Delaunay triangulation. With an inverse stereographic projection, this question translates to asking which combinatorial types of polytopes admit realizations with all the vertices on a d-sphere. We will construct a large family of neighborly polytopes that are not only inscribable on the sphere, but also in every smooth strictly convex body. This provides the current best lower bound for the number of combinatorial types of Delaunay triangulations. In the second part of the talk, we will use these techniques to show that realization spaces of inscribed polytopes present Universality in the sense of Mnëv. For example, this will allow us to construct a pair of point configurations whose Delaunay triangulations are combinatorially equivalent but yet there is no continuous transformation that maps one to the other without changing the combinatorics of the Delaunay triangulation.

This talk reports joint work with Karim Adiprasito, Bernd Gonska and Louis Theran.

23 octobre 2014
Julien Baste (Projet AlGCo, LIRMM, Montpellier)
Problèmes de connectivité paramétrés par la treewidth

Dans cette présentation nous nous intéresserons à des problèmes "de connexité" paramétrés par la treewidth. Tous les problèmes évoqués sont solubles par des algorithmes classiques en un temps 2^{O(tw log tw)}*poly(n). Nous nous intéresserons à l'algorithme de Cut&Count [1] réduisant ce temps de calcul pour la plupart de ces problèmes à un temps 2^{O(tw)}*poly(n) dans les graphes généraux puis examinerons les liens et les différences de complexité de ces problèmes de connexité entre les graphes généraux et les graphes planaires.

[1] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving connectivity problems parameterized by treewidth in single exponential time. FOCS 2011.

Travail en commun avec Ignasi Sau.

16 octobre 2014
Marc Noy (Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya (UPC))
Logical limit laws in combinatorics

Let A be a class of combinatorial structures equipped, for each N, with a probability distribution on the collection of objects of size N. Given a sentence S in some logical language, we are interested in the limiting probability P(S) that S is satisfied among all objects of size N, as N goes to infinity. If P(S) is either 0 or 1 for each sentence S, we say that the zero-one law holds. The first result of this kind was obtained by Glebskii et al. in 1969 for the class of labelled graphs and sentences in first order logic (FO). Compton (1987) obtained in some cases zero-one laws solely from properties of the counting function of the class A. Later he extended it to monadic second order logic (MSO), which is FO logic plus quantification over unary relations. More recently McCoy (2002) proved a zero-one law in MSO logic for labelled trees. We provide a significant extension of McCoy’s result to classes of graphs closed under taking minors. As an example, we prove the MSO zero-one law for connected planar graphs and a convergence law (every sentence has a limit, not necessarily 0 or 1) for all planar graphs. We also determine the closure of the set of all possible limiting probabilities, both in FO and MSO. For the proofs we use classical tools from combinatorial logic, in particular Ehrenfeucht-Fraïssé games, and properties of random graphs from a minor-closed class.

09 octobre 2014
Isolde Adler (Institut für Informatik, Goethe Universität, Frankfurt, Germany)
PAC learning of FO definable concepts & nowhere dense graph classes

Let C be a graph class closed under subgraphs. We prove that all FO-definable concept classes on C allow example-efficient learnability (in the PAC model) if and only if C is nowhere dense.

02 octobre 2014
Guilherme D. da Fonseca (Équipe AlGCo, LIRMM, Montpellier)
On the ratio between perfect matchings and maximum weight matchings

Given a graph G that admits a perfect matching, the parameter eta(G) is defined as follows. Among all positive edge weight assignments, eta(G) is the minimum ratio between the maximum weight of (i) a perfect matching and (ii) any matching. In this talk we present new and previous results on the parameter eta. Among them, a characterization of graphs with eta(G)=0 and eta(G) = 1 and the exact value of eta for all grids, bipartite cylindrical grids, and bipartite toroidal grids.

Joint work with: Diana Sasaki and Bernard Ries.

25 septembre 2014
Jean-Florent Raymond (LIRMM (Montpellier, France) and University of Warsaw (Poland))
Packings induits de cycles

Deux cycles d'un graphes sont mutuellement induits s'il n'y a pas d'arêtes entre eux dans le graphe. Etant donné un graphe G et un entier r, peut-on facilement savoir si G contient r cycles 2 à 2 induits ? Ce problème, que nous appellerons Cycles-Induits, n'a pas de noyau polynomial quand il est paramétrisé par r sous des hypothèses courantes de complexité, d'après les résultats de Bodlaender, Thomassé et Yeo (2012), qui ont étudié sa version non-induite.

En utilisant des arguments simples, nous montrons que Cycles-Induits a un noyau de taille O(Δ²) pour r = 2 et O(rΔ² log(rΔ)) pour r > 2. Une conséquence est que la version non-induite du problème a aussi un noyau polynomial pour cette paramétrisation.

Résultats obtenus en collaboration avec Aistis Atminas (Université de Warwick) et Marcin Kamiński (Université de Varsovie).

18 septembre 2014
Mickael Montassier (AlGCo, LIRMM, Montpellier)
Cycles and Colourings: problem session

Cet exposé sera la présentation des problèmes ouverts posés lors du workshop "Cycles and Colourings 2014".

04 septembre 2014
Dimitrios M. Thilikos (CNRS, AlGCo, LIRMM, Montpellier)
Optimal Erdős-Pósa for pumpkins: vertex and edge variants and approximation algorithms

The origin of the study of Erdős-Pósa properties comes from the celebrated Erdős-Pósa Theorem (1965), stating that there is a natural function $f$ such that for every positive integer $k$ and for every graph $G$, either $G$ contains $k$ vertex-disjoint cycles or there is a set $X$ of $f(k)$ vertices in $G$ meeting all cycles of $G$. In particular, Erdős and Pósa proved this result for $f(k)=O(k\cdot \log k)$ and showed that this bound is optimal. Given a graph $J$, we denote by ${\cal M}(J)$ the set of all graphs that can be contracted to $J$ (also called models of $J$). Robertson and Seymour proved that the class ${\cal M}(J)$ satisfies the Erdős-Pósa property if and only if $J$ is planar. Notice that this can be seen as a major extension of the Erdős-Pósa Theorem (take $J=\theta_{2}$ where, in general, $\theta_{r}$ is the graph consisting of two vertices and $r$ parallel edges between them). The emerging question is whether (and when) the function involved in the above proposition can match the (optimal) $O(k\cdot \log k)$ bound of Erdős-Pósa and whether this bound can be improved under several assumptions on the graphs it applies. Given two graphs $H$ and $G$, we denote by ${\bf pack}^{\sf v}_{H}(G)$ (resp. ${\bf pack}^{\sf e}_{H}(G)$) the maximum number of vertex (resp. edge)-disjoint models of $H$ in $G$. We also denote by ${\bf cover}^{\sf v}_{H}(G)$ resp. ${\bf cover}^{\sf v}_{H}(G)$) the minimum number of vertices (resp. edges) that intersect all models of $H$ in $G$.

We give a unified proof of the following result.

Theorem: For every ${\sf x}\in\{{\sf v},
{\sf e}\}$, there exists a function $f:\Bbb{N}\rightarrow\Bbb{N}$ such that for every two positive integers $r,q$ and every graph $G$ excluding $K_{q}$ as a minor, it holds that ${\bf cover}^{\sf x}_{\theta_{r}}(G)\leq f(r)\cdot {\bf pack}^{\sf x}_{\theta_{r}}(G)\cdot \log q$.

Our results also imply that, for every ${\sf x}\in\{{\sf v},
{\sf e}\}$ and $r$, the problems of computing the values of ${\bf pack}^{\sf x}_{\theta_{r}}$ and ${\bf cover}^{\sf x}_{\theta_{r}}$, admit $\log(OPT)$-approximation (deterministic and polynomial) algorithms. This improves existing results on the approximability for the case where ${\sf x}={\sf v}$.

(Joint work with: Dimitris Chatzidimitriou, Jean-Florent Raymond, and Ignasi Sau).