## 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é
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)- 21/03/24 - Mathieu Mari : Shortest Disjoint Paths on a Grid
- 14/03/24 - Maximilian Gorsky : Packing even directed circuits quarter-integrally
- 07/03/24 - Raul Wayne Teixeira Lopes : New Menger-like dualities in digraphs and applications to half-integral linkages
- 29/02/24 - Petra Wolf : Kernelizing Temporal Exploration Problems
- 15/02/24 - Samuel Braunfeld : Some interactions between model theory and structural graph theory
- 08/02/24 - Aliaume Lopez : Locality and the Łoś–Tarski Theorem in Finite Model Theory
- 11/01/24 - Júlio Araújo : Semi-proper orientations of dense graphs
- 07/12/23 - Chien-Chung Huang : Robust Sparsification for Matroid Intersection with Applications
- 30/11/23 - Oscar Defrain : Minimal dominating sets enumeration with FPT-delay parameterized by the (degeneracy and) maximum degree
- 19/10/23 - Christophe Paul : Linear time modular decomposition algorithm
- 12/10/23 - Laure Morelle : An introduction to odd-minors
- 05/10/23 - Timothé Picavet : A parameterized approximation scheme for the 2D-Knapsack problem with wide items
- 05/10/23 - Timothé Picavet : Locally approximating dominating sets in K_{2,t}-minor-free graphs
- 21/09/23 - Ana Silva : Menger-related Problems on Temporal Graphs
- 29/06/23 - Dimitrios M. Thilikos : Universal Obstructions of Graph Parameters
- 08/06/23 - Open Problem Session : Open Problem Session of AlGCo Team
- 11/05/23 - Clément Maria : Parameterized complexity in low dimensional topology
- 27/04/23 - Hoang La : Boolean dimension of boolean lattices
- 20/04/23 - Cléophée Robin : A Closure Lemma for tough graphs and Hamiltonian degree conditions (14h30)
- 13/04/23 - Mathieu Mari : A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangle
- 06/04/23 - Hugo Jacob : On the parameterized complexity of computing tree-partitions
- 30/03/23 - Alexandre Talon : The complexity of colouring graphs without C4's or stable sets of size 4: a story with a C++ program
- 23/03/23 - Nofar Carmeli : Query answering: tractability beyond acyclicity
- 16/03/23 - William Lochet : Minimum-Membership Geometric Set Cover for unit squares
- 09/03/23 - Giannos Stamoulis : Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
- 16/02/23 - Petr A. Golovach : Shortest cycles with monotone submodular costs
- 08/02/23 - Aliaume Lopez : Locality and the Łoś–Tarski Theorem in Finite Model Theory
- 02/02/23 - Noleen Kölher : Twin-Width VIII: Delineation and Win-Wins
- 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
The well-known k-disjoint paths problem involves finding pairwise The talk will end with some open questions related to the shortest Joint work with Anish Mukherjee, Michal Pilipczuk and Piotr Sankowski.
We prove the existence of a computable function f : N → N such that for every integer k and every digraph D either contains a collection C of directed cycles of even length such that no vertex of D belongs to more than four cycles in C, or there exists a set S ⊆ V (D) of size at most f(k) such that D − S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time $g(k)\cdot n^{O(1)}$ for some computable function g : N → N. Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and
We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of congestion two (or any other constant) from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger's Theorem on appropriately defined auxiliary digraphs, and an alternative simpler one using matroids, however with worse polynomial running time. As an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs 𝒢 = (G₁, G₂, … , G_L) that share a common vertex set but might have different edge sets. The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the k-arb NS-TEXP problem, where the agent’s task is to visit at least k vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor k-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices n, lifetime L, number of vertices to visit k, and maximal number of connected components per time step γ; as well as in the combined parameters L+k, L + γ, and k+γ. On the way to establishing these lower bounds, we answer a couple of questions left open by Erlebach and Spooner. We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph p(𝒢) = ∑_{i=1}^L (|E(G_i)|) - |V(G)| + 1. Informally, this parameter measures how dynamic the temporal graph is. Our main algorithmic result is the construction of a polynomial (in p(𝒢)) kernel for the more general Weighted k-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least k. This talk is based on joined work together with Emmanuel Arrighi, Fedor V. Fomin, and Petr A. Golovach
We will discuss how model-theoretic concepts concerned with separating tame from wild behavior in classes of infinite structures and with developing a structure theory for the tame classes can be applied to classes of finite structures, interacting with programs in structural graph theory. In particular, these concepts have been behind significant recent progress in determining when the general algorithmic problem of first-order model checking is fixed-parameter tractable.
Preservation theorems are classical results from Model Theory, stating that syntactic fragments of first-order logic (existential sentences, existential positive sentences, etc) are characterised by semantic properties (sentences preserved under extensions, preserved under injective homomorphisms, etc). The status of these results in finite model theory (that is, restricting the statement to classes of finite structures) is non trivial. Indeed, the classical proofs of these results rely on the compactness theorem of first-order logic, which is known to fail in the finite. Furthermore, on restricted classes of structures, semantic characterisations become weaker (for instance, it is easier to be preserved under extensions when fewer structures belong to the class), and syntactic equivalences become weaker too (more sentences are equivalent when tested over fewer models). Understanding over which classes of finite structures preservation theorems relativise involves tools from finite model theory (locality of first order logic), requires combinatorial results (mainly about the spatial distribution of types of neighbourhoods in finite structures), and even features some usage of monadic second order logic. While preservation theorems are interesting in themselves (because they have connections with well-quasi-orders, and characterise termination of some database algorithms such as the Chase), their study also provides deep insight into which classes of structures are “well-behaved” with respect to first-order logic. In this talk, we will focus on one particular preservation theorem, the Łoś–Tarski Theorem, and prove that this theorem relativises to a class 𝒞 of finite structures if and only if it relativises locally to the class 𝒞, which will illustrate the aforementioned techniques. This talk is based on the results published at LICS 2022 in the paper “When Locality Meets Preservation”.
An A In this work, we first prove that $spo(G) \in \{ω(G)-1,ω(G)\}$ for every split graph $G$, and that, given a split graph $G$, deciding whether $spo(G) = ω(G)-1$ is an $NP$-complete problem. We also show that, for every $k$, there exists a (chordal) graph $G$ and a split subgraph $H$ of $G$ such that $po(G) ≤ k$ and $po(H) = 2k-2$. In the sequel, we show that, for every $n≥ p(p+1)$, $spo(P^{p}_n) = \left\lceil \frac{3}{2}p \right\rceil$, where $P^{p}_n$ is the $p^{th}$ power of the path on $n$ vertices. We investigate further unit interval graphs with no big clique: we show that $po(G) ≤ 3$ for any unit interval graph $G$ with $ω(G)=3$, and present a complete characterization of unit interval graphs with $po(G)=ω(G)=3$. Then, we show that deciding whether $spo(G)=ω(G)$ can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing $spo(G)$ is FPT when parameterized by the minimum size of a vertex cover in $G$ or by the treewidth of $G$. We also prove that not only computing $spo(G)$, but also $po(G)$, admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size $4^{{\cal O}(k^2)}$ and ${\cal O}(2^kk^2)$, in chordal graphs and split graphs, respectively, for the problem of deciding whether $spo(G)≤ k$ parameterized by $k$. We also present exponential kernels for computing both $po(G)$ and $spo(G)$ parameterized by the value of the solution when $G$ is a cograph. On the other hand, we show that computing $spo(G)$ does not admit a polynomial kernel parameterized by the value of the solution when $G$ is a chordal graph, unless NP $\subseteq$ coNP/poly. Joint work with F. Havet, C. Linhares Sales, N. Nisse and K. Suchan.
Matroid intersection is a classical optimization problem where, given two matroids over the same ground set, the goal is to find the largest common independent set. We show how to construct a certain ``sparsifer'': a subset of elements, of size $O(|S^{opt}| \cdot 1/\varepsilon)$, where $S^{opt}$ denotes the optimal solution, that is guaranteed to contain a $3/2 + \varepsilon$ approximation, while guaranteeing certain robustness properties. We call such a small subset a
At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an $n^{O(d)}$-delay algorithm listing all minimal transversals of an n-vertex hypergraph of degeneracy $d$. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether this XP-delay algorithm parameterized by d could be made FPT-delay parameterized by $d$ and the maximum degree Δ, i.e., an algorithm with delay $f(d,Δ)⋅n^{O(1)}$ for some computable function f. Moreover, as a first step toward answering that question, they note that the same delay is open for the intimately related problem of listing all minimal dominating sets in graphs. In this paper, we answer the latter question in the affirmative. Joint work with Valentin Bartier and Fionn Mc Inerney
There is a long history of modular decomposition algorithms starting in the 70’s with a $O(n^4)$ algorithm. The first linear time algorithms appeared in 1994 (by Cournier, Habib and by McConnell, Spinrad). Since them simplified (almost) linear time algorithms have been proposed. I will describe one based on LexBFS and a tree-partition refinement technique. The complexity analysis requires a carefully amortized analysis that we will discuss. This is a joint work with D. Corneil, M. Habib and M. Tedder that was originally presented at ICALP’08, but which full version is still lacking.
Odd-minors, which are essentially minors preserving the parity of
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA'19] showed that it is also W[1]-hard when parameterized by the size k of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90° before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. We make progress towards this goal by showing a PAS under the following assumptions: 1. both the box and all the input rectangles have integral, polynomially bounded sidelengths; 2. every input rectangle is wide -- its width is greater than its height; and 3. the aspect ratio of the box is bounded by a constant. Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.
The field of distributed algorithms studies algorithms that are designed to run on different computers simultaneously, without any shared memory. We focus on the so-called LOCAL model, where computers are part of a network and work together to solve a problem (in our case Minimum Dominating Set) on the network itself. The LOCAL model is used to study the locality in network computing, to determine which problems can be solved when every computer only knows a part of the network (in our case a constant radius region) before outputting. As finding a constant-factor approximation of MDS is not possible on general graphs, we will focus on minor forbidden classes, particularly the class of $K_{2,t}$-minor-free graphs. We give a $(2t-1)$-approximation for MDS on this class, which breaks the non-exponential approximation factor barrier. This also generalizes and simplifies the involved proof of the 5 approximation factor for outerplanar graphs.
A temporal graph is a graph that changes in time, meaning that, at each timestamp, only a subset of the edges is active. This structure models all sorts of real-life situations, from social networks to public transportation, having been used also for contact tracing during the COVID pandemic. Despite its broad applicability, and despite being around for more than two decades, only recently this structure has received more attention from the community. In this talk, we will discuss how to bring some connectivity concepts to the temporal context, and we will learn about the state of the art of complexity results of the related problems. Additionally, we will see various possible adaptations of Menger’s Theorem, only a few of which also hold on temporal graphs. The results presented in this talk were obtained in collaboration with Allen Ibiapina (Universidade Federal do Ceará, Brazil), Raul Lopes (École Normale Supérieure de Paris, France) and Andrea Marino (University of Florence, Italy).
We introduce the notion of universal obstruction of a graph parameter, with respect to some quasi-ordering relation. Universal obstructions may serve as compact characterizations of the asymptotic behavior of graph parameters. We provide order-theoretic conditions which imply that such a characterization is finite. We formally present the concepts of Universal Obstruction, Class Obstruction, and Parametric Obstruction. We also present some algorithmic implications on the existence of fixed-parameter algorithms. Joint work with Christophe Paul and Evangelos Protopapas
Open problems session of AlGCo-team
Parameterized complexity is a theory allowing a finer analysis of the complexity of algorithms, which was originally applied to graph problems. In this talk, I will survey recent results on the use of parameters for algorithmic and combinatorial topology, with a focus on knots and 3-manifolds. I will try to motivate and highlight the particular flavor of parameterized complexity when applied to the computation of quantum invariants. I will also illustrate some of the techniques to connect combinatorial and topological parameters, and design algorithms, at the interface of topology, classical and quantum computational complexity, and combinatorics.
Dimension is often defined as a measure of complexity of a poset. In that sense, boolean dimension is an even more compact way of encoding a poset. Moreover, behind each directed graph G, there exists a corresponding poset such that its boolean realizer gives a reachability labeling scheme for G. In an effort to better understand this measure, we study the boolean dimension for boolean lattices where the question of the equality of its Dushnik-Miller dimension and boolean dimension is open. We answer this question in the negative and provide lower and upper bounds for boolean dimension of boolean lattices.
A graph G is hamiltonian if it exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G − S is at most |S| / t. We extended the Theorem of Hoàng by proving the following : Let G be a graph with degree sequence d_1,d_2,…,d_n and let t be a positive integer at most 4. If G is t-tough and if. ∀ i, t ≤ i <n/2, d_i ≤ i ⇒ d_{n−i+t} ≥ n−i then G is hamiltonian. To do this we extend the closure lemma due to Bondy and Chvàtal. This is joint work with Chình T. Hoàng
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs), without intersecting certain special horizontal line segments called fences. In this talk, I will present a (2+ε)-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to 2+ε. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to O(1/ε) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR. At the end of the talk, I will present a bunch of future research directions related to the problem. This is a joint work with Waldo Gálvez, Arindam Khan, Tobias Mömke,
Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete, which is likely to exclude FPT algorithms. However, we prove that computing a tree-partition of approximate width is tractable using a relatively simple sketch. This is sufficient to remove the requirement of having a Based on joint work with Hans Bodlaender and Carla Groenland.
In this talk, we present a work in progress about the complexity of proper colouring in hereditary classes of graphs. This problem, central in structural graph theory, is known to be NP-complete in the general case. We will focus on the colouring problem restricted to the classes of graphs defined by a set of forbidden induced subgraphs. This is a joint work with Cléophée Robin and Marco Caoduro
Consider the task of enumerating the answers to natural join queries over databases.
The minimum-membership set cover (MMSC) problem is a variant of the traditional set cover problem. Given a universe S and a collection of sets R, the goal of MMSC is to select a subset R of R such that every element in S is covered by R. Instead of minimizing the size of R as in the usual set cover problem, the goal of MMSC is to minimize the maximum degree of an element of S in R. This problem was introduced by Kuhn et al. in 2005, where they gave a log(n) approximation in polynomial time and showed that it was the best approximation ratio we could hope for under standard complexity assumptions. This is based on joint work with S. Bandyapadhyay, S. Saurabh, and J. Xue.
The Joint work with Petr Golovach and Dimitrios M. Thilikos
We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function $f$ defined on the vertices (or, equivalently, the edges) of an undirected graph $G$, we seek for a cycle $C$ in $G$ of minimum cost $Opt=f(C)$. We construct an algorithm that, given an $n$-vertex graph $G$, parameter $ε > 0$, and the function $f$ represented by an oracle, in time $n^{O(\log 1/ε)}$ finds a cycle $C$ in $G$ with $f(C)\leq (1+ε)Opt$. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest $(s,t)$-Path problem, which requires exponentially many queries to the oracle for finding an $n^{2/3-ε}$-approximation [Goel et al., FOCS 2009]. When the function $f$ is integer-valued, our algorithm yields that a cycle of cost $Opt$ can be found in time $n^{O(\log Opt)}$. In particular, for $Opt=n^{O(1)}$ this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Joint work with: Fedor V. Fomin, Tuukka Korhonen, Daniel Lokshtanov, and Giannos Stamoulis
Preservation theorems are classical results from Model Theory, stating that syntactic fragments of first-order logic (existential sentences, existential positive sentences, etc) are characterised by semantic properties (sentences preserved under extensions, preserved under injective homomorphisms, etc). The status of these results in finite model theory (that is, restricting the statement to classes of finite structures) is non trivial. Indeed, the classical proofs of these results rely on the compactness theorem of first-order logic, which is known to fail in the finite. Furthermore, on restricted classes of structures, semantic characterisations become weaker (for instance, it is easier to be preserved under extensions when fewer structures belong to the class), and syntactic equivalences become weaker too (more sentences are equivalent when tested over fewer models). Understanding over which classes of finite structures preservation theorems relativise involves tools from finite model theory (locality of first order logic), requires combinatorial results (mainly about the spatial distribution of types of neighbourhoods in finite structures), and even features some usage of monadic second order logic. While preservation theorems are interesting in themselves (because they have connections with well-quasi-orders, and characterise termination of some database algorithms such as the Chase), their study also provides deep insight into which classes of structures are “well-behaved” with respect to first-order logic. In this talk, we will focus on one particular preservation theorem, the Łoś–Tarski Theorem, and prove that this theorem relativises to a class 𝒞 of finite structures if and only if it relativises locally to the class 𝒞, which will illustrate the aforementioned techniques. This talk is based on the results published at LICS 2022 in the paper “When Locality Meets Preservation”.
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 M. 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)$. |