AlGCo : algorithmes, graphes et combinatoire

Responsable : Emeric Gioan

Département Informatique - LIRMM

Accueil | Annonces | Membres | Projets | Visiteurs | Publications | 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 - - (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é
19 mai 2022 (salle : )
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.

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)

16 juin 2022 (salle : Bât 4, salle du séminaire (LIRMM - RDC Entrée))
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 (salle : E.3.23 Bâtiment 4 LIRMM,
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 (salle :
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 (salle : )
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

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

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