# AlGCo : algorithmes, graphes et combinatoire

### Département Informatique - LIRMM

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

Séminaire

En général (sauf exception), le séminaire/groupe de travail AlGCo a lieu le jeudi de 10h à 11h (et quelques) en salle de séminaire bât. 4 ou sur ZOOM - https://www.lirmm.fr/algco/GT/zoom - (en période covid).

Contact : Dimitrios Thilikos

Abonnement à la liste de diffusion algocomb : ici (annonces des exposés du LIRMM et de l'IMAG en algorithmique, combinatoire et mathématiques discrètes).

Fichier ICalendar (pour avoir l'information du séminaire AlGCo directement dans son agenda) : ici.

La page ci-dessous est générée automatiquement à partir de la page du séminaire sur collorg.

Prochain exposé
 02 février 2023 (salle : E.3.23 Bâtiment 4 LIRMM, https://www.lirmm.fr/algco/GT/zoom)
 Noleen Kölher (LMSADE, Paris) Twin-Width VIII: Delineation and Win-Wins

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC ’22] and permutation graphs [BKTW, JACM ’22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated.
In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA ’21]. We show that Kt,t-free segment graphs, and axis-parallel Ht-free unit segment graphs have bounded twin-width, where Ht is the half-graph or ladder of height t. In contrast, axis-parallel H4-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated.

More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM ’22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) · |V (G)|O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.

Joint work with Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Raul Lopes and Stéphan Thomassé.

Exposés (à venir)

Archives : 2021-... | 2018-2021 | 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 (passés depuis 09/2021)

 02 février 2023 (salle : E.3.23 Bâtiment 4 LIRMM, https://www.lirmm.fr/algco/GT/zoom)
 Noleen Kölher (LMSADE, Paris) Twin-Width VIII: Delineation and Win-Wins

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC ’22] and permutation graphs [BKTW, JACM ’22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated.
In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA ’21]. We show that Kt,t-free segment graphs, and axis-parallel Ht-free unit segment graphs have bounded twin-width, where Ht is the half-graph or ladder of height t. In contrast, axis-parallel H4-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated.

More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM ’22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) · |V (G)|O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.

Joint work with Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Raul Lopes and Stéphan Thomassé.

 26 janvier 2023
 Théo Pierron (LIRIS, Université Lyon 1) Extremal Independent Set Reconfiguration

The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. The goal is usually to find short transformations for graphs of a given class. Here, we take an alternative, more extremal point of view by asking a reverse question: which graphs yield (shortest) transformations of maximum length?

This is joint work with Nicolas Bousquet, Bastien Durain, and Stéphan Thomassé.

 12 janvier 2023
 Sebastian Wiederrecht (Discrete Mathematics Group, Institute for Basic Science, Daejeon, South Korea) Excluding Single-Crossing Matching Minors in Bipartite Graphs

By a seminal result of Valiant, computing the permanent of $(0,1)$-matrices is, in general, $\#\mathsf{P}$-hard. In 1913 Pólya asked for which $(0,1)$-matrices $A$ it is possible to change some signs such that the permanent of $A$ equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding $K_{3,3}$ as a \textsl{matching minor}. This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond $K_{3,3}.$ Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the \textsl{permanent} of the corresponding $(0,1)$-matrices can be computed efficiently. In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and $K_{3,3}$ which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains $\#\mathsf{P}$-hard on bipartite graphs which exclude $K_{5,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem, we obtain a strict generalisation of the algorithm for the $k$-vertex disjoint directed paths problem on digraphs of bounded directed treewidth.

Joint work with Archontia C. Giannopoulou and Dimitrios M. Thilikos

 05 janvier 2023
 Marin Bougeret (Équipe AlGCo, LIRMM) Kernelization for Graph Packing Problems via Rainbow Matching

We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021}].
We apply the rainbow matching technique on two (di)graph packing problems, namely the Triangle-Packing in Tournament problem (TPT), where we ask for a directed triangle packing in a tournament, and the Induced 2-Path-Packing (IPP) where we ask for a packing of $k$ induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomassé, Zehavi. ACM Trans. Algorithms, 2019], where they gave a kernel of ${\cal O}(k^{3/2})$ vertices and ${\cal O}(k^{5/3})$ vertices respectively. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT admits an (almost linear) kernel of $k^{1+\frac{O(1)}{\sqrt{\log{k}}}}$ vertices
and that IPP admits kernel of ${\cal O}(k)$ vertices.

Joint work with Stéphane Bessy, Dimitrios M. Thilikos, and Sebastian Wiederrecht

 15 décembre 2022
 Michel Habib (Research Institute on the Foundations of Computer Science (IRIF) - Paris Cité University) Graph searches, discrete geometric convexities and greediness

We show some of the links between properties of graph searches used to recognize hereditary classes of graphs and discrete geometric convexities. Not only this framework unifies many scattered results but also it allows to consider many new interesting problems. Moreover we consider greediness yielded by some graph searches (such as the lexicographic ones) and show how to use this greediness to solve optimization problems.

Joint work with Feodor Dragan (Kent, USA) and Lalla Mouatadib (Toronto, Canada)

 01 décembre 2022
 Benjamin Bergougnoux (Faculty of Mathematics, Informatics, and Mechanics - University of Warsaw) Tight Lower Bounds for Problems Parameterized by Rank-width

We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan, Telle, and Vatshelle [Discret. Appl. Math., 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math., 2021]. We also show that the known $2^{O(k^2)} n^{O(1)}$ time algorithms for Weighted Dominating Set, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width $k$ are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for $n$-vertex graphs.

 24 novembre 2022
 Nicole Schirrmacher (Universität Bremen) Separator logic and disjoint-paths logic on topological-minor-free graphs

The well-known theorem of Courcelle states that every problem expressible in monadic second-order logic is fixed-parameter tractable on classes of graphs with bounded treewidth. A more recent result of Grohe, Kreutzer and Siebertz shows that every problem expressible in first-order logic is fixed-parameter tractable on classes of nowhere dense graphs. We try to close the gap between first-order logic and monadic second-order logic by new logics such as separator logic and disjoint-paths logic. We show that every problem expressible in separator logic or disjoint-paths logic is fixed-parameter tractable on classes of graphs that exclude a fixed graph as a topological minor.

This talk is based on joint work with Michał Pilipczuk, Sebastian Siebertz, Giannos Stamoulis, Dimitrios Thilikos, Szymon Toruńczyk and Alexandre Vigny

 10 novembre 2022
 Yann Marin (Équipe AlGCo, LIRMM) On transversal matroid and the Pascal Matroid

We introduce some important notion of (non oriented) matroid on an interesting example that appear on the tiling of the (finite) triangular lattice by rhombus. Let T(n) be an equilateral triangle of size n made by n(n+1)/2 black triangles and n(n-1)/2 white triangles. We will show how all the set B of n black triangles such that T(n)/B is tillable by bicolored rhombus are related to a matroid. We will then discuss some of its important properties and how it is surprisingly related to a particular cellular automata problem. The core of this part is the relation between matching in bipartite graph and the bases of a transversal matroid.

 10 novembre 2022
 Yann Marin (Équipe AlGCo, LIRMM) Introduction to convexity in oriented matroid for oriented graph

We introduce the notion of convexity in oriented matroid and focus on how it applies to oriented graph. We will introduce some core definition of usual convex geometry such as face, convex hull etc... then we may look at what mean some important convexity theorem in an oriented graph and expose some problem we are interested in. For this part we will alternate between digraph properties and oriented matroid properties, it will illustrate the differences and the similitudes of the two structures.

 27 octobre 2022
 Evangelos Protopapas (Équipe AlGCo, LIRMM) Tree-layout based graph classes: the case of proper chordal graphs

Many standard graph classes are known to be characterized by means of layouts (a permutation of its vertices) excluding some patterns. Important such graph classes are proper interval graphs, interval graphs, chordal graphs but also permutation graphs, (co-)comparability graphs and so on. For example, a graph $G=(V,E)$ is an interval graph if and only if $G$ has a layout $\mathbf{L}$ such that for every triple of vertices such that $x\prec_{\mathbf{L}} y\prec_{\mathbf{L}} z$, if $xz\in E$, then $xy\in E$. We call such a layout an interval layout. Proper interval graphs are characterized by excluding indifference triples, defined as triples $x\prec_{\mathbf{L}} y\prec_{\mathbf{L}} z$ such that if $xz\in E$, then $xy\in E$ and $yz\in E$. In this talk, we investigate the concept of tree-layouts. A tree-layout $\mathbf{T}$ of a graph $G=(V,E)$ is a rooted tree $(T,r)$ equipped with a one-to-one mapping between $V$ and the node of $T$ such that for every edge $xy\in E$, either $x$ is an ancestor of $y$, denoted $x\prec_{\mathbf{T}} y$, or $y$ is an ancestor of $x$. Excluding a pattern in a tree-layout is defined similarly as excluding a pattern in a layout, but now using the ancestor relation. It can be easily observed that chordal graphs are characterized by the existence of a tree-layout that excludes the interval pattern discussed above. As a proof of concept, we show that excluding indifference triples in tree-layouts yields a natural graph class of proper chordal graphs. We will position proper chordal graphs with respect to other known graph classes and explore its structural and algorithmic aspects.

Joint work with Christophe Paul

 13 octobre 2022
 Laure Morelle (Équipe AlGCo, LIRMM) Faster parameterized algorithms for modification problems to minor-closed classes

Let ${\cal G}$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $G$ is a $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$. Our first result is an algorithm that decides whether $G$ is a $k$-apex of ${\cal G}$ in time $2^{{\sf poly}(k)}\cdot n^2$, where poly is a polynomial function depending on ${\cal G}$.

This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020], whose running time was $2^{{\sf poly}(k)}\cdot n^3$.

The elimination distance of $G$ to ${\cal G}$, denoted by ${\sf ed}_{\cal G}(G)$, is the minimum number of rounds required to reduce each connected component of $G$ to a graph in ${\cal G}$ by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] provided an FPT-algorithm, with parameter $k$, to decide whether ${\sf ed}_{\cal G}(G)\leq k$. This algorithm is based on the computability of the minor-obstructions and its dependence on $k$ is not explicit. We extend the techniques used in the first algorithm to decide whether ${\sf ed}_{\cal G}(G)\leq k$ in time $2^{2^{2^{k^{O(1)}}}}\cdot n^2$. This is the first algorithm for this problem with an explicit parametric dependence in $k$. In the special case where ${\cal G}$ excludes some apex-graph as a minor, we give two alternative algorithms, one running in time $2^{2^{O(k^2\log k)}}\cdot n^2$ and one running in time $2^{{\sf poly}(k)}\cdot n^3$. As a stepping stone for these algorithms, we provide an algorithm that decides whether ${\sf ed}_{\cal G}(G)\leq k$ in time $2^{{\cal O}({\sf tw}\cdot k + {\sf tw}\log {\sf tw})}\cdot n$, where ${\sf tw}$ is the treewidth of $G$. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where ${\cal G}$ contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs ${\cal E}_k({\cal G})=\{G \mid {\sf ed}_{\cal G}(G)\leq k\}$.

Joint work with Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos

 22 septembre 2022
 Bertrand Marchand (LIX, École Polytechnique) Graph width parameters in RNA bioinformatics

An RNA consists of a chain of molecular blocks called nucleotides (A, U, G, C), resulting
from a transcription of a portion of a DNA strand. Although they are traditionally
thought of as mere intermediates in the synthesis of proteins, a subset of them,
dubbed functional RNAs, perform as such a wide variety of biological functions.

Their functions are largely determined by their 3D structures, i.e. the way nucleotides
are paired up in complex folding conformations. Understanding the connection between
the composition of a given sequence and its preferred folding conformations is therefore
key to understanding, or acting upon, many biological mechanisms.

RNA bioinformatics is then tasked with tackling several computational problems that naturally
arise from trying to understand this connection. The most natural one is folding: given
an RNA sequence, try to predict the structure(s) it will preferably adopt.
But one could also wonder about structure reconfiguration (how easy it is for
an RNA molecule to go from a folded structure to another ?) or structure-sequence
alignment (how compatible are a given fold and a given sequence ?).
All these problems are computationally hard,
especially when going towards realistic biological models.

This talk will focus on selected instances of such landmark problems, and on
current attempts to tackle them with exact parameterized algorithmics. A particular
focus will be given to graph algorithms, and graph width parameters. Examples
of graph problems emerging from this angle include minimum edge deletion towards
a target treewidth value [1], or the computation of directed pathwidth for a particular
geometric subset of directed graphs [2].

References:
[1] B. Marchand, Y. Ponty, L. Bulteau. Tree Diet: Reducing the Treewidth to Unlock
FPT Algorithms in RNA Bioinformatics. Algorithms for Molecular Biology 2022.

[2] L. Bulteau, B. Marchand, Y. Ponty. A new parameterization for independent set
reconfiguration and applications to RNA kinetics. IPEC 2021.

 15 septembre 2022
 Benjamin Merlin Bumpus (Eindhoven University of Technology,) Structured Decompositions: recursive data and recursive algorithms

What is recursive structure? And how can we exploit it algorithmically? In this talk I will give as general an answer to these questions as I can by calling upon the new notion of structured decompositions. This is a category-theoretic formalism that Jade Master, Zoltan Kocsis and I recently introduced which yields a vast generalisation of tree-width to arbitrary categories. I will explain — assuming no prior knowledge at all of category theory — how to make use of structured decompositions for three purposes: (1) defining new tree-width-like invariants, (2) relating these decompositions to each-other via functors and (3) how one might go about proving algorithmic meta-theorems using the language of category theory. This is ongoing, multidisciplinary work. As such it requires lots people with different types of expertise, so you should consider this talk is an invitation to get involved!

 30 juin 2022
 Dibyayan Chakraborty (ENS Lyon) Complexity of geometric intersection representation of apex graphs

Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles, line segments, L-shapes. For general graphs, however, even deciding whether such representations exist is often NP-hard.

We consider apex graphs, i.e., graphs that can be made planar by removing one vertex from them. We show, somewhat surprisingly, that deciding whether certain geometric representations exist for apex graphs is NP-hard.

Most known NP-hardness reductions for these problems are from variants of 3-SAT. We reduce from the PLANAR HAMILTONIAN PATH COMPLETION problem, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric graphs.

joint work with Kshitij Gajjar

 30 juin 2022
 Dibyayan Chakraborty (ENS Lyon) Approximation of isometric path cover

This talk about an algorithmic problem called Isometric Path Cover, where the objective is to cover the vertices of a graph using smallest number of isometric paths. We show that the problem is NP-hard even on chordal graphs and provide constant factor approximation algorithms for graphs with bounded tree-length.

 16 juin 2022
 Stavros Kolliopoulos (DIT, National and Kapodistrian University of Athens) Precedence-Constrained Covering Problems with Multiplicity Constraints

We study the approximability of covering problems when the set of
items chosen to satisfy the covering constraints must be a prefix of a
given partial order. We examine the general case with multiplicity
constraints, where item $i$ can be chosen up to $d_i$ times. For the
basic Precedence-Constrained Knapsack problem (PCKP) we answer an open
question of McCormick et al. and show the existence of approximation
algorithms with strongly-polynomial bounds.

PCKP is a special case, with a single covering constraint, of a
Precedence-Constrained Covering Integer Program (PCCP). For a general
PCCP where the number of covering constraints is $m \geq 1,$ we show
that an algorithm of Pritchard and Chakrabarty for Covering Integer
Programs can be extended to yield an $f$-approximation, where $f$ is
the maximum number of variables with nonzero coefficients in a
covering constraint. This is nearly-optimal under standard
complexity-theoretic assumptions and rather surprisingly matches the
bound known for the problem without precedence constraints.

Joint work with Antonis Skarlatos.

 09 juin 2022
 Daniel Gonçalves (Équipe AlGCo) On comparable box dimension

Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset
of a translation of the other. The comparable box dimension of a graph
$G$ is the minimum integer $d$ such that $G$ can be represented as a
touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We
show that proper minor-closed classes have bounded comparable box
dimension and explore further properties of this notion. In particular we show that graphs with bounded comparable box dimension are treewidth fragile.

Joint work with Z. Dvořák, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

 02 juin 2022
 Lars Jaffke (UiB, Bergen) A logic-based algorithmic meta-theorem for mim-width

We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (A&C DN for short) which extends existential MSO1 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed A&C DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions.

Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length.

Joint work with Benjamin Bergougnoux and Jan Dreier.

 19 mai 2022
 Maximilian Gorsky (Technische Universität Berlin) Matching Theory, Hamiltonicity, and Barnette's Conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.

A graph is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. [Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs, JCTB, 1985]. These allow us to check whether a graph we generated is a brace.

Joint work with Sebastian Wiederrecht und Raphael Steiner.

 11 mai 2022
 Robert Ganian (Technische Universität Wien, Institute of Logic and Computation) Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts

Decompositional parameters such as treewidth are commonly used to
obtain fixed-parameter algorithms for NP-hard graph problems. For
problems that are W[1]-hard parameterized by treewidth, a natural
alternative would be to use a suitable analogue of treewidth that is
based on edge cuts instead of vertex separators. While tree-cut width
has been coined as such an analogue of treewidth for edge cuts, its
algorithmic applications have often led to disappointing results: out
of twelve problems where one would hope for fixed-parameter
tractability parameterized by an edge-cut based analogue to treewidth,
eight were shown to be W[1]-hard parameterized by tree-cut width.

Here, we will discuss an edge-cut based analogue to treewidth called
edge-cut width. Edge-cut width is, intuitively, based on measuring the
density of cycles passing through a spanning tree of the graph. Its
benefits include not only a comparatively simple definition, but
mainly that it has interesting algorithmic properties: it can be
computed by a fixed-parameter algorithm, and it yields fixed-parameter
algorithms for all the aforementioned problems where tree-cut width
failed to do so.

 28 avril 2022
 Raul Wayne (Dauphine Paris) Adapting the Directed Grid Theorem into an FPT algorithm

The Grid Theorem of Robertson and Seymour [JCTB, 1986] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001], and proved by Kawarabayashi and Kreutzer [STOC, 2015]. They showed that there is a function $f(k)$ such that every digraph of directed tree-width at least $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor. Their constructive proof can be turned into an XP algorithm, with parameter $k$, that either constructs a decomposition of the appropriate width or finds the claimed large cylindrical grid as a butterfly minor.

In this talk, we present the ideas we used to adapt the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter $k$. The first one either produces an arboreal decomposition of width $3k-2$ or finds a $(k-1)$-linked set in a digraph $D$, improving on the original result for arboreal decompositions by Johnson et al. [JCTB, 2001]. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k whose vertices appear in a path hitting all elements of $B$. As a tool to prove these results, we also show how to solve a generalized version of the problem of finding balanced separators for a set of vertices $T$ in FPT time with parameter $|T|$.

Joint work with Victor Campos, Ana Karolinna Maia, and Ignasi Sau.

 21 avril 2022
 Petr Golovach (UiB, Bergen) Longest Cycle above Erdős-Gallai Bound

In 1959, Erdős and Gallai proved that every graph $G$ with average vertex degree $\mathsf{ad}(G)≤ 2$ contains a cycle of length at least $\mathsf{ad}(G)$. We provide an algorithm that for $k\geq 0$ in time $2^{O(k)} n^{O(1)}$ decides whether a 2-connected n-vertex graph G contains a cycle of length at least $\mathsf{ad}(G)+k$. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

Joint work with Fedor V. Fomin, Danil Sagunov, and Kirill Simonov.

 14 avril 2022
 Michał Włodarczyk (Eindhoven University of Technology) Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion

In the $\mathcal{F}$-minor-free deletion problem we want to find a minimum vertex set in a given graph that intersects all minor models of graphs from the family $\mathcal{F}$. The Vertex planarization problem is a special case of $\mathcal{F}$-minor-free deletion for the family $\mathcal{F} = {K_5, K_{3,3}}$. Whenever the family $\mathcal{F}$ contains at least one planar graph, then $\mathcal{F}$-minor-free deletion is known to admit a constant-factor approximation algorithm and a polynomial kernelization [Fomin, Lokshtanov, Misra, and Saurabh, FOCS'12]. The Vertex planarization problem is arguably the simplest setting for which $\mathcal{F}$ does not contain a planar graph and the existence of a constant-factor approximation or a polynomial kernelization remains a major open problem.
In this work we show that Vertex planarization admits an algorithm which is a combination of both approaches. Namely, we present a polynomial $A$-approximate kernelization, for some constant $A > 1$, based on the framework of lossy kernelization [Lokshtanov, Panolan, Ramanujan, and Saurabh, STOC'17]. Simply speaking, when given a graph $G$ and integer $k$, we show how to compute a graph $G'$ on $\mathsf{poly}(k)$ vertices so that any $B$-approximate solution to $G'$ can be lifted to an $(A\cdot B)$-approximate solution to $G$, as long as $A\cdot B\cdot {\rm OPT}(G) ≤ k$. In order to achieve this, we develop a framework for sparsification of planar graphs which approximately preserves all separators and near-separators between subsets of the given terminal set. Our result yields an improvement over the state-of-art approximation algorithms for Vertex planarization. The problem admits a polynomial-time $O(n^ε)$-approximation algorithm, for any $ε > 0$, and a quasi-polynomial-time $(\log n)^{O(1)}$ approximation algorithm, both randomized [Kawarabayashi and Sidiropoulos, FOCS'17]. By pipelining these algorithms with our approximate kernelization, we improve the approximation factors to respectively $O({\rm OPT}^ε)$ and $(\log {\rm OPT})^{O(1)}$.

Joint work with Bart Jansen

 07 avril 2022
 Jean Florent Raymond (LIMOS, Université Clermont Auvergne) Long induced paths in minor-closed graph classes and beyond

In this paper we show that every graph of pathwidth less than k that has a path of order n also has an induced path of order at least $\frac{1}{3}n^{1/k}$. This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by Esperet, Lemoine and Maffray (2016) for interval graphs of bounded clique number. We complement this result with an upper-bound.
This result is then used to prove the two following generalizations:
- every graph of treewidth less than k that has a path of order n contains an induced path of order at least $\frac{1}{4}(\log n)^{1/k}$;
- for every non-trivial graph class that is closed under topological minors there is a constant $d∈(0,1)$ such that every graph from this class that has a path of order n contains an induced path of order at least $(\log n)^d$.
We also describe consequences of these results beyond graph classes that are closed under topological minors.

Joint work with Claire Hilaire.

 31 mars 2022
 Eunjung Kim (LAMSADE, CNRS) Twin-width and the algorithmic implications

A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced graph invariant called the twin-width is based on contraction sequences [BKTW, J. ACM ’22]. More precisely, if one puts error edges, henceforth red edges, between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer d such that a contraction sequence, called d-sequence, exists that keeps red degree at most d. Many well-known graph classes are shown to have bounded twin-width including unit interval graphs, a strict hereditary class of permutation graphs, posets of bounded width, proper minor-closed class, subgraphs of O(1)-dimensional grids as well as graphs of bounded tree-width and clique-width. Since its introduction two years ago, twin-width gained extensive traction across areas such as graph theory, algorithms design, logic, data structure, constraint programming and communication complexity.

In this talk, we review some algorithmic implications of twin-width on graphs of bounded twin-width and beyond such graphs.

It was proved in [BKTW, JACM ’22] that FO (first-order) model-checking is fixed-parameter tractable provided that a d-sequence is given. This unifies and extends known tractability results. Due to its generality, the running time of FO model-checking algorithm suffers a huge dependency on the (nested) quantifier depth of the input sentence. It turns out that for concrete well-known problems such as k-Dominating Set, k-Independent Set and Subgraph Isomorphism in general, slick dynamic programming can be designed so that the runtime dependency is single exponential in k provided O(1)-sequence is given [BGKTW, ICALP ’21]. The spirit of such DP algorithms is further extended in [BKRT, SODA ’22] to attain an alternative proof for the tractability MSO model-checking on graph of bounded clique-width [Courcelle, Makowsky, Rotics, TCS ’00].

The terrain of monotone (closed under taking subgraphs) graph classes is fully charted in regards to fixed-parameter tractability of FO model-checking: a monotone graph class is nowhere dense if and only if FO model-checking is fpt on it. For the more general hereditary (closed under taking induced subgraphs) graph classes, it is conjectured that a class admits an fpt algorithm for FO model-checking if and only the class “does not encode all finite graphs in a manner interpretable by FO logic” (monadically dependent). We survey a few graph classes where the conjecture is positively affirmed and the dividing line is drawn precisely by the twin-width. Such classes include ordered graphs [BGdMST, STOC ’22], permutation graphs [BKTW, JACM ’22] and circle graphs [Hlinený, Filip Pokrývka, '22], interval graphs and rooted directed path graphs [BCKKLT, ’22].

Twin-width can be useful for designing algorithms even on graph classes of unbounded twin-width. Some structures like large bicliques, half-graphs, or independent sets are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Combined with the FPT algorithm for FO model checking on graphs given with O(1)-sequences, this give rise to a variety of algorithmic win-win arguments [BCKKLT, ’22]. For instance, we readily derive fpt algorithms for k-Independent Set on visibility graphs of simple polygons, which was addressed as an open problem

 24 mars 2022
 Giannos Stamoulis (Équipe AlGCo, LIRMM) Paths and Cycles of Large Rank in Frameworks

We provide fixed-parameter tractable (FPT) algorithms for the following generalization of the fundamental Longest Path and Longest Cycle problems. Following Lovász, we call by a framework a pair $(G,M)$, where $G$ is an undirected graph and $M$ is a matroid whose elements are the vertices of $G$. Then for a framework $(G,M)$ and integer $k$, the Max Rank Path/Cycle problem asks whether there is a path/cycle in $G$ whose vertices form a set of rank at least $k$ in $M$.
Max Rank Path/Cycle encompasses several fundamental problems about paths and cycles in graphs. When $M$ is a uniform matroid of rank $|V(G)|$, then Max Rank Path/Cycle becomes the problem of finding a path (or cycle) with at least $k$ vertices, one of the most studied problems in parameterized complexity. Other notable special cases of Max Rank Path/Cycle are the problems of finding a cycle containing at least $k$ terminal vertices and a path in a colored graph containing at least $k$ different colors.
The main results of our paper are two theorems about Max Rank Path/Cycle. The first theorem gives a randomized FPT algorithm when matroid $M$ is representable over a finite field (with parameter $k$ and the order of the field). This implies, for example, the first FPT algorithm for finding a path containing at least $k$ different colors. The second theorem establishes a deterministic FPT algorithm for planar graphs and matroids representable over finite fields or rationals.

Joint work with Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen.

 17 mars 2022
 Elisabet Burjons (TCS RWTH) Lower Bounds for Conjunctive and Disjunctive Turing Kernels

The non-existence of polynomial kernels for OR- and AND-compositional problems is now a well-established result. Some of these problems have adaptive or non-adaptive polynomial Turing kernels. Up to now, most known polynomial Turing kernels are non-adaptive and most of them are of the conjunctive or disjunctive kind. For some problems it has been conjectured that the existence of polynomial Turing kernels is unlikely. For instance, either all or none of the WK[1]-complete problems have polynomial Turing kernels. While it has been conjectured that they do not, a proof tying their non-existence to some complexity theoretic assumption is still missing and seems to be beyond the reach of today’s standard techniques.
We proved that OR-compositional problems and all WK[1]-hard problems do not have conjunctive polynomial kernels, a special type of non-adaptive Turing kernels, under the assumption that coNP ⊈ NP/poly. Similarly, it is unlikely that AND-compositional problems have disjunctive polynomial kernels. Moreover, we present a way to prove that the parameterized versions of some ⊕ P-hard problems, for instance, Odd Path on planar graphs, do not have conjunctive or disjunctive polynomial kernels, unless coNP ⊆ NP/poly.

Joint work with Peter Rossmanith

 10 mars 2022
 Hoang LA (Équipe AlGCo, LIRMM) The potential method in graphs with a bounded maximum average degree

Theorems on graphs with bounded maximum average degree (mad) often employ the discharging method since it transforms the general bounded ratio between edges and vertices in the graph into local counting arguments and structures that are easier to study. Most of the time, the bounded mad only serves as a counting tool for the discharging procedure. However, improvements in this method often consists in finding new reducible configurations (configurations that cannot appear in a minimal counter-example). The potential method fits the bill perfectly as it introduces a function that quantifies exactly the mad surrounding a local structure. This addition allows for a better manipulation of the mad in the reduction of new configurations. This talk will introduce the concept of basic operations with the potential function in the class of graphs with bounded mad.

 24 février 2022
 Meike Hatzel (Technische Universität Berlin Institut für Softwaretechnik und Theoretische Informatik) On the structure of directed graphs

In their series of over twenty papers Robertson and Seymour give insight into the structure of undirected graphs. Proving a number of impactful theorems they arrive at the structure theorem, a description of graphs excluding a fixed non-planar minor. A lot of work has been done in recent years trying to transfer such results to a directed setting. In this attempt one encounters numerous obstacles.
In this talk we consider these obstacles and possibilities to deal with them.
We take a look at the current state of digraph structure theory with respect to proving a structure theorem for excluding a fixed butterfly minor.

 17 février 2022
 Ioan Todinca (Université d’Orléans, LIFO - Laboratoire d’informatique fondamentale d’Orléans) A Meta-Theorem for Distributed Certification

Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and for every certificate assignment, at least one process rejects. The verification of the certificates must be fast, and the certificates themselves must be small. A large quantity of results have been produced in this framework, each aiming at designing a distributed certification mechanism for specific boolean predicates. This paper presents a "meta-theorem", applying to many boolean predicates at once. Specifically, we prove that, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs, there exists a distributed certification mechanism using certificates on $O(\log^2n)$ bits in n-node graphs of bounded treewidth, with a verification protocol involving a single round of communication between neighbors.

 10 février 2022
 Martin Koutecký (Computer Science Institute, Faculty of Mathematics and Physics, Charles University) Liquid Democracy for Participatory Budgeting

Liquid Democracy is a form of delegative democracy which promises more direct participation and dynamic representation. Because it is only recently become realistic with the use of modern technologies, it has been coming into the focus of research. We propose a model of liquid democracy in the context of participatory budgeting. A common issue in the context of liquid democracy is the resolution of delegation cycles -- if the vote of A depends on B, which depends on C, which depends on A, how should they vote? We define several natural notions of proportionality and show that delegations in our model can always be satisfactorily resolved.

Next, we turn to the computational aspects of our model. By known results, the complexity of finding a proportional delegation belongs to the class PPAD. Rather than showing completeness or tighter containment (in classes such as PLS, CLS etc.), we ask the practical question: is it possible to efficiently resolve delegations in "real-world" instances? We design an algorithm which seems to perform well. In the absence of real-world instances, we also devise a framework to compute hard instances; this framework might be of independent interest.

 03 février 2022
 Zdeněk Dvořák (Computer Science Institute of Charles University,) Approximation meta-algorithms [Déplacé/Moved: 15:00–16:00]

For a monotone property $π$ of subsets of vertices of a graph $G$ (being an independent set, forming a clique in $G^2$, ...), let $MAX_π(G)$ denote the size of the largest subset of $V(G)$ having this property. By a fundamental result of Grohe, Kreutzer, and Siebertz, if $π$ is expressible in the first-order logic, then $MAX_π$ is fixed-parameter tractable for graphs from any nowhere-dense class (when parameterized by the value of the solution). We survey results on a related question: In which graph classes does $MAX_π$ admit efficient approximation algorithms?

 27 janvier 2022
 Sebastian Wiederrecht (Équipe AlGCo, LIRMM) Killing a Vortex

The Structural Theorem of the Graph Minors series of Robertson and Seymour asserts that, for every $t\in\Bbb{N}$, there exists some constant $c_{t}$ such that every graph minor-excluding $K_{t}$ admits a tree decomposition, of adhesion at most $c_{t}$, whose torsos can be transformed, by the removal of at most $c_{t}$ vertices, to graphs that can be seen as the union of some graph that is embeddable to some surface of genus at most $c_{t}$ and "at most $c_{t}$ vortices of depth $c_{t}$''. Our main combinatorial result is a "vortex-free'' refinement of the above structural theorem as follows: we identify a universal graph called shallow vortex grid $H_{t}$ and we prove that if, in the above structural theorem, we replace $K_{t}$ by $H_{t}$, then the resulting decompositions become "vortex-free''. Up to now, the most general classes of graphs admitting such a result were either bounded genus graphs or the so called single-crossing minor-free graphs. Our result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some $H_{t}$, the appearance of vortices is unavoidable. Using the above decomposition theorem, we prove that, on $H_{t}$-minor-free graphs, the generating function of perfect matchings can be computed in polynomial time. This algorithm yields, on $H_{t}$-minor-free graphs, polynomial algorithms for computational problems such as the dimer problem, the exact matching problem, and the computation of the permanent. Our results, combined with known complexity results, imply a complete characterization of minor-closed graphs classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every $H_{t}$ as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.

Joint work with Dimitrios Thilikos

 20 janvier 2022
 Tuukka Korhonen (UiB, Bergen) A Single-Exponential Time 2-Approximation Algorithm for Treewidth

We give an algorithm, that given an $n$-vertex graph $G$ and an integer $k$, in time $2^{O(k)} n$ either outputs a tree decomposition of $G$ of width at most $2k+1$ or determines that the treewidth of G is larger than $k$. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms. In particular, our algorithm improves upon both the previous best approximation ratio of 5 in time $2^{O(k)} n$ and the previous best approximation ratio of 3 in time $2^{O(k)} n^{O(1)}$, both given by Bodlaender et al. [SICOMP 2016]. Our algorithm is based on a local improvement method adapted from a proof of Bellenbaum and Diestel [Comb. Probab. Comput. 2002].

 13 janvier 2022
 Dimitrios Thilikos (Équipe AlGCo, LIRMM) Θ-logic and Algorithmic meta-theorems: When big kingdoms fall from within

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. We propose a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in monadic second-order logic and have models of bounded treewidth, while target sentences express first-order logic properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or ${\cal G}$-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model checking can be done in quadratic time. This algorithmic meta-theorem encompasses, unifies, and extends all known meta-algorithmic results on minor-closed graph classes. Moreover, all derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle's theorem does not apply.

Joint work with Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, and Giannos Stamoulis

 06 janvier 2022
 William Lochet (Équipe AlGCo, LIRMM) Disjoint paths on dense graphs

In this talk we will see the proof that the $k$-edge disjoint paths problem can be solved in polynomial time on graphs with minimum degree $αn$ provided $k$ is small enough (but still linear in $n$). In particular this implies a linear kernel on the class of graphs with linear minimum degree, which is not possible on general graphs.

Joint work with Lokshtanov, Saurabh and Zehavi

 16 décembre 2021
 Mamadou Moustapha Kanté (LIMOS, Université Clermont Auvergne) Letter graphs: Characterisation, recognition and relations with geometric grid classes of permutations

We will present the graph parameter lettericity, which roughly tells how a graph looks like a word on a fixed alphabet and give some examples of bounded/unvounded lettericity. Letter graphs enjoy nice properties, in particular they are well-quasi-ordered under induced subgraphs. We propose a combinatorial characterisation and propose from this an MS-definability of graphs of lettericity k, for fixed k, and a bound on the number of vertices of an obstruction. The MS-definability implies also a cubic FPT-recognition algorithm. In a second step we introduce the notion of geometric grid permutations, which are permutations that can be mapped on a grid and that enjoy very nice properties (well-quasi-order, algebraicity, etc.). We show that a geometric permutation class has bounded griddability iff its permutations graphs have bounded lettericity.

This is a joint work with B. Alecu, R. Ferguson, V. Lozin, V. Vatter and V. Zamaraev.

 09 décembre 2021
 Édouard Bonnet (MC2, LIP, ENS Lyon) Twin-width of matrices and ordered graphs

The twin-width of a graph $G$ can be defined as the least integer $d$ such that there is a sequence of length $|V(G)|$ of (strictly) coarser and coarser partitions of its vertex set $V(G)$, and every part $X$ of every partition $P$ of the sequence has at most d other parts $Y$ of $P$ with both at least one edge and at least one non-edge between $X$ and $Y$. Twin-width is closely tied to total orders on the vertices, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures, or if you prefer, matrices on a finite alphabet. This turns out to be key in understanding combinatorial, algorithmic, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows. Enumerative combinatorics: All the classes of 0,1-matrices with superexponential growth have growth at least n!. Algorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded. Finite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same. In addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum, which is still missing for unordered graphs.

Joint work with Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk.

 02 décembre 2021
 Amadeus Reinald (ENS de Lyon - 4A Informatique Fondamentale) Twin-width: forbidden subdivisions and polynomial kernels

Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, FO model checking is FPT when provided with a sequence witnessing the bound. In this talk, we first explore the structure implied by large twin-width in terms of induced subdivisions, to then look at the existence of polynomial kernels on classes of bounded twin-width.

Structurally, the understanding of graph parameters in terms of induced subgraphs, rather than minors, is an active area of research. For treewidth, an induced analogue of the grid minor theorem could be that, for sparse graphs, large treewidth implies the existence of an induced subdivision of a large wall. However, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2,3}$). Abrishami, Chudnovsky, Hajebi and Spirkl have recently shown that such (theta, triangle)-free classes have nevertheless logarithmic treewidth. Through a structural "Connected-BFS" decomposition, we show that theta-free graphs of girth at least 5 have bounded twin-width.

We then study the existence of polynomial kernels for k-Dominating Set and variants of k-Vertex Cover on classes of bounded twin-width. Our main result is that k-Dominating Set admits no polynomial kernel on graphs of twin-width at most 4. On the positive side, we leverage a VC-density argument on classes of bounded twin-width to show that Connected k-Vertex Cover and Capacitated k-Vertex Cover admit $O(k^1.5)$ and $O(k^2)$ kernels respectively.

Joint work with Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant.

 25 novembre 2021
 Alexandre Vigny (University of Bremen) Separator logic, expressive power and algorithmic applications

First-order logic (FO) can express many algorithmic problems on graphs, but fails to express whether two vertices are connected. We define a new logic (separator logic) by enriching FO with connectivity predicates ${\sf conn}_k(x, y, z_1, . . . , z_k)$ that hold true in a graph if there exists a path between x and y after deletion of $z_1, . . . , z_k$.

Joint work with Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, and Szymon Toruńczyk

 04 novembre 2021
 Sang-Il Oum (엄상일) (Institute for Basic Science (IBS) & KAIST) Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field 𝔽, the list contains only finitely many 𝔽-representable matroids, due to the well-quasi-ordering of 𝔽-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these 𝔽-representable excluded minors in general.
We consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field 𝔽, every 𝔽-representable excluded minor for the class of matroids of path-width at mostk has at most $2^{|𝔽|^{O(k^2)}}$ elements. We can therefore compute, for any integer k and a fixed finite field 𝔽, the set of 𝔽-representable excluded minors for the class of matroids of path-width $k$, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an 𝔽-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.

This is joint work with Mamadou M. Kánte, Eun Jung Kim, and O-joung Kwon.

 28 octobre 2021
 Alexandros Singh (CALIN, Laboratoire d'Informatique de Paris Nord, Université Sorbonne Paris Nord) Asymptotic Distribution of Parameters in Trivalent Maps and Linear Lambda Terms

Structural properties of large random maps and lambda-terms may be gleaned by studying the limit distributions of various parameters of interest. In our work we focus on restricted classes of maps and their counterparts in the lambda-calculus, building on recent bijective connections between these two domains. In such cases, parameters in maps naturally correspond to parameters in lambda-terms and vice versa. By an interplay between lambda-terms and maps, we obtain various combinatorial specifications which allow us to access the distributions of pairs of related parameters such as: the number of bridges in rooted trivalent maps and of subterms in closed linear lambda-terms, the number of vertices of degree 1 in (1,3)-valent maps and of free variables in open linear lambda-terms etc. To analyse asymptotically these distributions, we introduce appropriate tools: a moment-pumping schema for differential equations and a composition schema inspired by Bender's theorem.

Joint work with Olivier Bodini and Noam Zeilberger

 21 octobre 2021
 Kenny Štorgel (Faculty of Information Studies in Novo mesto, Slovenia) Further Extensions of the Grötzsch Theorem

The Grötzsch Theorem states that every triangle-free planar graph $G$ admits a proper $3$-coloring, i.e. a coloring of the vertices of $G$ with three colors such that adjacent vertices are assigned distinct colors. However, we may also allow triangles in general planar graphs and still retain $3$-colorability. Havel conjectured that a $3$-colorable planar graph may contain arbitrarily many triangles as long as they are sufficiently far apart. This conjecture was proved by Dvořák, Kráľ, and Thomas. On the other hand, there are $3$-colorable planar graphs that may have close triangles (even incident). A result by Dross et al. states that every planar graph obtained as a subgraph of the medial graph of a bipartite plane graph is $3$-colorable.
As mentioned, the Grötzsch Theorem has many generalizations, although, perhaps the most well-known is a result of Grünbaum and Aksenov, giving $3$-colorability of planar graphs with at most three triangles, which is in general best possible. A lot of attention was also given to extending $3$-colorings of subgraphs of triangle-free planar graphs to the whole graph. In particular, a result of Aksenov, Borodin, and Glebov states that we can precolor any two non-adjacent vertices in a triangle-free planar graph and retain $3$-colorability. Furthermore, several other results exist which deal with precolorings of a face of certain length in a triangle-free planar graph.
In this talk, we will present the above-mentioned results and provide further extensions of the Grötzsch Theorem by considering $3$-colorings of planar graphs with at most one triangle. In particular, we show that a precoloring of any two non-adjacent vertices and a precoloring of a face of length at most $4$ can be extended to a $3$-coloring of the whole graph. Additionally, we show that for every vertex of degree at most $3$ in a planar graph with at most one triangle, a precoloring of its neighborhood with the same color extends to a $3$-coloring of the whole graph. The latter result yields an affirmative answer to a conjecture on adynamic coloring.

 14 octobre 2021
 Thi Viet Ha Nguyen (Inria Sophia Antipolis, I3S) Graph problems motivated by (low and high) resolution models of large protein assemblies.

Our works focus on graph problems motivated by structural biology issues. A macromolecular assembly consists in a set of subunits, each subunit may have a lot of configurations and any subunit is linked to the others by some relations.
At a low resolution, given a set of subunits, or complexes of the assembly (where each complex is a subset of subunits), it simply specifies the interaction of subunits in an assembly. The graph problem is then given a hypergraph $H$ with a set of vertices $V(H)$ and a set of hyperedges $E(H)$ (each hyperedge is a subset of vertices), and asks to find a graph on $V(H)$ satisfying some constraints (bounded degree, local structures).
At a high resolution, given an assembly and a set of configurations for each subunit, the problem consists in finding a set of configurations for all subunits, under some constraints. Then the graph problem is given a graph and a set of colors for each vertex, to find a coloring which satisfies some objective function (generalization of $k$-coloring, called conflict coloring).
We will present our studies on these two graph problems. The results are mainly about complexity, then some algorithms and experiments for the second problem.

Joint works with Frédéric Cazals, Frédéric Havet, Dorian Mazauric and Rémi Watrigant.

 07 octobre 2021
 Sebastian Wiederracht (Équipe AlGCo, LIRMM) The Flat Wall Theorem for Bipartite Graphs with Perfect Matchings

Matching minors are a specialized version of minors fit for the study of graphs with perfect matchings. The first major appearance of matching minors was in a result by Little who showed that a bipartite graph is Pfaffian if and only if it does not contain $K_{3,3,}$ as a matching minor. Later it was shown, that $K_{3,3,}$-matching minor free bipartite graphs are, apart from a single exception, essentially bipartite planar graphs glued together at 4-cycles. We generalize these ideas by giving an approximate description of bipartite graphs excluding $K_{t,t}$ as a matching minor in the spirit of the famous Flat Wall Theorem of Robertson and Seymour. In essence, we show that every bipartite $K_{t,t}$-matching minor free graph is locally $K_{3,3}$-matching minor free after removing an apex set of bounded size.

 30 septembre 2021
 Martin Milanič (Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska in Koper, Slovenia) Tree Decompositions with Bounded Independence Number

Which graphs admit a tree decomposition such that each bag induces a subgraph with bounded independence number? When available, such a tree decomposition can be used to solve the Maximum Weight Independent Set (MWIS) problem in polynomial time. We consider six graph containment relations: the subgraph, topological minor, and minor relations, as well as their induced variants, and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number.

As our main result, we obtain an infinite family of graph classes that admit polynomial-time algorithms for the MWIS problem. All but two of these graph classes form a proper generalization of the class of chordal graphs, and hence this result is a significant strengthening of the polynomial-time solvability of the MWIS problem for the class of chordal graphs given by Frank in 1976. Another consequence is that the MWIS problem is solvable in polynomial time in the class of $1$-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius [WADS 2019].

Joint work with Clément Dallard and Kenny Štorgel.

 23 septembre 2021
 Vasiliki Velona (Einstein Institute of Mathematics, Hebrew University of Jerusalem) Learning partial correlation graphs and graphical models by covariance queries

We study the problem of recovering the structure underlying large Gaussian graphical models or, more generally, partial correlation graphs. In high-dimensional problems, it is often too costly to store the entire sample covariance matrix. We propose a new input model in which one can query single entries of the covariance matrix. We prove that it is possible to recover the support of the inverse covariance matrix with low query and computational complexity. Our algorithms work in a regime when this support is represented by tree-like graphs and, more generally, for graphs of small treewidth. Our results demonstrate that for large classes of graphs, the structure of the corresponding partial correlation graphs can be determined much faster than even computing the empirical covariance matrix.

The results of the talk are joint work with Gábor Lugosi, Jakub Truszkowski, and Piotr Zwiernik.

 16 septembre 2021
 Fabien Jacques (Équipe AlGCo, LIRMM) Complexity of 3 + 1/m-coloring Pt-free graphs

The 4-coloring problem is NP-complete for $P_7$-free graphs whereas the 3-coloring problem can be solved in quasi-polynomial time on $P_t$-free graphs for any fixed t. We consider circular coloring to locate precisely the complexity gap between 3 and 4 colors: for every fixed integer m ≥ 2, the 3 + 1/m-coloring problem is NP-complete on $P_30$-free
graphs.

 09 septembre 2021
 William Lochet (Department of Informatics, University of Bergen) EPTAS for k-means Clustering of Affine Subspaces

Clustering is one of the most widely used techniques in data mining, statistics, and machine learning. In general, the purpose of clustering is to group a set of objects such that similar objects end up in the same cluster. A common approach to clustering is to treat objects with $d$ features as points in $\mathbb{R}^d$ and the measure of the similarity between two objects is the Euclidian distance between the corresponding points. One of the most famous mathematical models of data clustering is $k$-means. In $k$-means clustering, we want to partition the points in $\mathbb{R}^d$, or some other metric space, by selecting a set of $k$ centers and assign each of the points to its closest center. The quality of the clustering solution is characterized by the $k$-means cost function, which minimizes the sum of squared distances between every point and its nearest center. Here we consider a generalization of $k$-means clustering for data with incomplete or corrupted entries. When data objects are represented by points in $\mathbb{R}^d$, a data point is said to be incomplete when some of its entries are missing or unspecified. An incomplete data point with at most $\Delta$ unspecified entries corresponds to an axis-parallel affine subspace of dimension at most $\Delta$, called a $\Delta$-point. Thus we seek a partition of $n$ input $\Delta$-points into $k$ clusters minimizing the $k$-means objective. For $\Delta=0$, when all coordinates of each point are specified, this is the usual $k$-means clustering. We give an algorithm that finds an $(1+\epsilon)$-approximate solution in time $f(k,\epsilon, \Delta) \cdot n^2 \cdot d$ for some function $f$ of $k,\epsilon$, and $\Delta$ only. Our algorithm is a generalization of Kumar et al. algorithm for the usual $k$-means clustering and a large part of the talk will be spent explaining that algorithm.

This is joint work with E. Eiben, F. Fomin, P. Golovach, F. Panolan, and K. Simonov

The paper can be found https://arxiv.org/abs/2010.09580

 02 septembre 2021
 Claire Hilaire (LaBRI, Université de Bordeaux) Graph Major of Graph Drawing

Motivated by the Grid-Minor Theorem of Robertson and Seymour, a.k.a. the Excluded Grid Theorem, we study the following problem on the relation between graph drawings and grid minors: for any given planar graph $H$ with a polyline drawing on a $p\times q$ grid, what is the smallest area $A = A(p,q)$ of a grid having $H$ as minor?

Since $H$ is a planar graph with at most $pq$ vertices, a classical result in Graph Minor Theory implies that $H$ is minor of a square grid of side $2pq-4$, yielding the upper bound $A(p,q) = O( (pq)^2 )$. More recently, Dieng and Gavoille showed that $A(p,q) = O(p^2 q)$, leaving open the question whether $A(p,q) = O(p q)$ or not. This upper bound would be optimal since clearly $A(p,q) \ge pq$ if $H$ is a $p \times q$ grid.

In this study, we proved that finding the smallest area of a grid having $H$ as minor is NP-hard, and also that $A(p,q) = O(pq)$ holds for several large classes of $n$-vertex planar graphs with dense drawing, i.e., with drawing area $O(n)$.