## AlGCo : algorithmes, graphes et combinatoire
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).
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é
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. 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 Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Raul Lopes and Stéphan Thomassé. 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)- 26/01/23 - Théo Pierron : Extremal Independent Set Reconfiguration
- 12/01/23 - Sebastian Wiederrecht : Excluding Single-Crossing Matching Minors in Bipartite Graphs
- 05/01/23 - Marin Bougeret : Kernelization for Graph Packing Problems via Rainbow Matching
- 15/12/22 - Michel Habib : Graph searches, discrete geometric convexities and greediness
- 01/12/22 - Benjamin Bergougnoux : Tight Lower Bounds for Problems Parameterized by Rank-width
- 24/11/22 - Nicole Schirrmacher : Separator logic and disjoint-paths logic on topological-minor-free graphs
- 10/11/22 - Yann Marin : On transversal matroid and the Pascal Matroid
- 10/11/22 - Yann Marin : Introduction to convexity in oriented matroid for oriented graph
- 27/10/22 - Evangelos Protopapas : Tree-layout based graph classes: the case of proper chordal graphs
- 13/10/22 - Laure Morelle : Faster parameterized algorithms for modification problems to minor-closed classes
- 22/09/22 - Bertrand Marchand : Graph width parameters in RNA bioinformatics
- 15/09/22 - Benjamin Merlin Bumpus : Structured Decompositions: recursive data and recursive algorithms
- 30/06/22 - Dibyayan Chakraborty : Complexity of geometric intersection representation of apex graphs
- 30/06/22 - Dibyayan Chakraborty : Approximation of isometric path cover
- 16/06/22 - Stavros Kolliopoulos : Precedence-Constrained Covering Problems with Multiplicity Constraints
- 09/06/22 - Daniel Gonçalves : On comparable box dimension
- 02/06/22 - Lars Jaffke : A logic-based algorithmic meta-theorem for mim-width
- 19/05/22 - Maximilian Gorsky : Matching Theory, Hamiltonicity, and Barnette's Conjecture
- 11/05/22 - Robert Ganian : Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
- 28/04/22 - Raul Wayne : Adapting the Directed Grid Theorem into an FPT algorithm
- 21/04/22 - Petr Golovach : Longest Cycle above Erdős-Gallai Bound
- 14/04/22 - Michał Włodarczyk : Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
- 07/04/22 - Jean Florent Raymond : Long induced paths in minor-closed graph classes and beyond
- 31/03/22 - Eunjung Kim : Twin-width and the algorithmic implications
- 24/03/22 - Giannos Stamoulis : Paths and Cycles of Large Rank in Frameworks
- 17/03/22 - Elisabet Burjons : Lower Bounds for Conjunctive and Disjunctive Turing Kernels
- 10/03/22 - Hoang LA : The potential method in graphs with a bounded maximum average degree
- 24/02/22 - Meike Hatzel : On the structure of directed graphs
- 17/02/22 - Ioan Todinca : A Meta-Theorem for Distributed Certification
- 10/02/22 - Martin Koutecký : Liquid Democracy for Participatory Budgeting
- 03/02/22 - Zdeněk Dvořák : Approximation meta-algorithms [Déplacé/Moved: 15:00–16:00]
- 27/01/22 - Sebastian Wiederrecht : Killing a Vortex
- 20/01/22 - Tuukka Korhonen : A Single-Exponential Time 2-Approximation Algorithm for Treewidth
- 13/01/22 - Dimitrios Thilikos : Θ-logic and Algorithmic meta-theorems: When big kingdoms fall from within
- 06/01/22 - William Lochet : Disjoint paths on dense graphs
- 16/12/21 - Mamadou Moustapha Kanté : Letter graphs: Characterisation, recognition and relations with geometric grid classes of permutations
- 09/12/21 - Édouard Bonnet : Twin-width of matrices and ordered graphs
- 02/12/21 - Amadeus Reinald : Twin-width: forbidden subdivisions and polynomial kernels
- 25/11/21 - Alexandre Vigny : Separator logic, expressive power and algorithmic applications
- 04/11/21 - Sang-Il Oum (엄상일) : Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
- 28/10/21 - Alexandros Singh : Asymptotic Distribution of Parameters in Trivalent Maps and Linear Lambda Terms
- 21/10/21 - Kenny Štorgel : Further Extensions of the Grötzsch Theorem
- 14/10/21 - Thi Viet Ha Nguyen : Graph problems motivated by (low and high) resolution models of large protein assemblies.
- 07/10/21 - Sebastian Wiederracht : The Flat Wall Theorem for Bipartite Graphs with Perfect Matchings
- 30/09/21 - Martin Milanič : Tree Decompositions with Bounded Independence Number
- 23/09/21 - Vasiliki Velona : Learning partial correlation graphs and graphical models by covariance queries
- 16/09/21 - Fabien Jacques : Complexity of 3 + 1/m-coloring Pt-free graphs
- 09/09/21 - William Lochet : EPTAS for k-means Clustering of Affine Subspaces
- 02/09/21 - Claire Hilaire : Graph Major of Graph Drawing
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. 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 Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Raul Lopes and Stéphan Thomassé.
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é.
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
We introduce a new kernelization tool, called Joint work with Stéphane Bessy, Dimitrios M. Thilikos, and Sebastian Wiederrecht
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)
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.
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
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.
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.
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 Joint work with Christophe Paul
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 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
An RNA consists of a chain of molecular blocks called nucleotides (A, U, G, C), resulting Their functions are largely determined by their 3D structures, i.e. the way nucleotides RNA bioinformatics is then tasked with tackling several computational problems that naturally This talk will focus on selected instances of such landmark problems, and on References: [2] L. Bulteau, B. Marchand, Y. Ponty. A new parameterization for independent set
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!
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
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.
We study the approximability of covering problems when the set of PCKP is a special case, with a single covering constraint, of a Joint work with Antonis Skarlatos.
Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset Joint work with Z. Dvořák, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt
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.
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.
Decompositional parameters such as treewidth are commonly used to Here, we will discuss an edge-cut based analogue to treewidth called
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.
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.
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. Joint work with Bart Jansen
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. Joint work with Claire Hilaire.
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
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 Joint work with Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen.
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. Joint work with Peter Rossmanith
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.
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.
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.
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.
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?
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 Joint work with Dimitrios Thilikos
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].
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 Joint work with Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, and Giannos Stamoulis
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
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.
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.
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.
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
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. This is joint work with Mamadou M. Kánte, Eun Jung Kim, and O-joung Kwon.
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
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.
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. Joint works with Frédéric Cazals, Frédéric Havet, Dorian Mazauric and Rémi Watrigant.
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.
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 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.
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.
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
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
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: 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)$. |