AlGCo : algorithmes, graphes et combinatoire

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

Séminaire

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

()

Eric Brandwein (Departamento de Computación, Universidad de Buenos Aires, Argentina)
Parameterized algorithms for thinness via the cluster module number

In 2007, Mannino et al. defined k-thin graphs as a generalization of interval graphs, and defined the thinness of a graph to be the minimum k such that the graph is k-thin. When given a k-thin representation of a graph, several NP-complete problems can be solved in XP time parameterized by k. In this work we define a new graph parameter that we call the cluster module number of a graph, which generalizes twin-cover and neighborhood diversity, and can be computed in linear time. We then present a linear kernel for the problem of calculating the thinness on graphs with bounded cluster module number. As a corollary, this results in a linear kernel for Thinness when the input graph has bounded neighborhood diversity, and exponential kernels when the input graph has bounded twin-cover or vertex cover. On the negative side, we observe that Thinness parameterized by treewidth, pathwidth, bandwidth, (linear) mim-width, clique-width, modular-width, or the thinness itself, has no polynomial kernel assuming NP ̸⊆ coNP/poly.

Joint work with Flavia Bonomo-Braberman and Ignasi Sau.

Amadeus Reinald (Équipe AlGCo)
Oriented trees in $O(k \sqrt{k})$-chromatic digraphs, a subquadratic bound for Burr's conjecture

In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph.
Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} - \frac{k}{2} + 1$ by Addario-Berry et al.

In this talk, we give the first subquadratic bound for Burr's conjecture, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)$ contains any oriented tree of order $k$.
Moreover, we provide improved bounds of $\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$.

Joint work with Stéphane Bessy and Daniel Gonçalves

Lucas De Meyer (Laboratoire d'Informatique en Image et Systèmes d'information (LIRIS), Lyon 1)
Edge-recoloring with non-increasing potential

Dota, Linial and Peled proposed an algorithm to generate uniformly at random proper (2n − 1)-edge-colorings of the complete graph $K_{2n}$. A version of this algorithm consists on a random walk that starts at an arbitrary colouring and at each step recolors one edge uniformly at random such that it reduces a defined potential φ. Based on simulations, they conjectured that this random walk in the (2n − 1)-edge-colourings of $K_{2n}$ almost surely reaches a proper edge-coloring, and that it does so in $O(n^4)$ steps. Our main result studies the algorithm for a number of colors larger than the maximum degree ∆, for all graphs. In particular, for k ≥ ∆ + 1, we prove that there is always a reconfiguration sequence from a k-edge-coloring to a proper k-edge-coloring that does not increase the potential φ.

Pierre Aboulker (Équipe Talgo, Département Informatique de l'ENS)
Clique number of tournaments

The dichromatic number of a digraph is the minimum integer k such that the set of vertices of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is the same as the dichromatic of the digraph obtained from G by replacing each edge by a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerned with chromatic number of undirected graphs have been generalised to digraphs via the dichromatic number. However, no concept of clique number for digraphs was available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and the chromatic number in undirected graphs. We will focus on studying the notion of chi-boundedness in particular.

Mathieu Mari (AlGCo)
Shortest Disjoint Paths on a Grid

The well-known k-disjoint paths problem involves finding pairwise
vertex-disjoint paths between k specified pairs of vertices within a
given graph if they exist. In the shortest k-disjoint paths problem one
looks for such paths of minimum total length. Despite nearly 50 years of
active research on the k-disjoint paths problem, many open problems and
complexity gaps still persist. A particularly well-defined scenario,
inspired by VLSI design, focuses on infinite rectangular grids where the
terminals are placed at arbitrary grid points. While the decision
problem in this context remains NP-hard, no prior research has provided
any positive results for the optimization version. In this talk I
present a fixed-parameter tractable (FPT) algorithm for this scenario.
It is important to stress that this is the first result achieving the
FPT complexity of the shortest disjoint paths problem in any, even very
restricted classes of graphs where we do not put any restriction on the
placements of the terminals.

The talk will end with some open questions related to the shortest
disjoint paths problem. This result appears in SODA'24.

Joint work with Anish Mukherjee, Michal Pilipczuk and Piotr Sankowski.

Maximilian Gorsky (TUB (Technische Universität Berlin))
Packing even directed circuits quarter-integrally

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.
Our result unites two deep fields of research from the algorithmic theory for digraphs: The study of the Erdős-Pósa property of digraphs and the study of the Even Dicycle Problem. The latter is the decision problem which asks if a given digraph contains an even dicycle and can be traced back to a question of Pólya from 1913. It remained open until a polynomial time algorithm was finally found by Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004; announced jointly at STOC 1997). The Even Dicycle Problem is equivalent to the recognition problem of Pfaffian bipartite graphs and has applications even beyond discrete mathematics and theoretical computer science. On the other hand, Younger’s Conjecture (1973), states that dicycles have the Erdős-Pósa property. The conjecture was proven more than two decades later by Reed, Robertson, Seymour, and Thomas (Combinatorica 1996) and opened the path for structural digraph theory as well as the algorithmic study of the directed feedback vertex set problem. Our approach builds upon the techniques used to resolve both problems and combines them into a powerful structural theorem that yields further algorithmic applications for other prominent problems.

Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and
Sebastian Wiederrecht

Raul Wayne Teixeira Lopes (AlGCo)
New Menger-like dualities in digraphs and applications to half-integral linkages

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

Petra Wolf (LaBRI, Universtiy of Bordeaux)
Kernelizing Temporal Exploration Problems

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

Samuel Braunfeld (Charles University, Prague)
Some interactions between model theory and structural graph theory

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.

Aliaume Lopez (ENS Paris-Saclay, CNRS, LMF)
Locality and the Łoś–Tarski Theorem in Finite Model Theory

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”.

Júlio Araújo (Federal University of Ceará)
Semi-proper orientations of dense graphs

An orientation $D$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation $D$ of a graph $G$ is a $k$-orientation if the in-degree of each vertex in $D$ is at most $k$. An orientation $D$ of $G$ is proper if any two adjacent vertices have different in-degrees in $D$. The proper orientation number of a graph $G$, denoted by $po(G)$, is the minimum $k$ such that $G$ has a proper $k$-orientation.

A weighted orientation of a graph $G$ is a pair $(D,w)$, where $D$ is an orientation of $G$ and $w$ is an arc-weighting $A(D) \to \mathbb{N}\setminus\{0\}$. A semi-proper orientation of $G$ is a weighted orientation $(D,w)$ of $G$ such that for every two adjacent vertices $u$ and $v$ in $G$, we have that $S_{(D,w)}(v) \neq S_{(D,w)}(u) $, where
$S_{(D,w)}(v)$ is the sum of the weights of the arcs in $(D,w)$ with head $v$. For a positive integer $k$, a semi-proper $k$-orientation $(D,w)$ of a graph $G$ is a semi-proper orientation of $G$ such that $\max_{v\in V(G)} S_{(D,w)}(v) ≤ k$. The semi-proper orientation number of a graph $G$, denoted by $spo(G)$, is the least $k$ such that $G$ has a semi-proper $k$-orientation.

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.

Chien-Chung Huang (École Normale Supérieure Ulm)
Robust Sparsification for Matroid Intersection with Applications

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 Density Constrained Subset (DCS), which is inspired by the Edge-Degree Constrained Subgraph (EDCS) [Bernstein and Stein, 2015], originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the density-based decomposition. We show that this sparsifier has certain robustness properties that can be used in one-way communication and random-order streaming models.

Oscar Defrain (LIS Laboratoire recherche informatique automatique systèmes Marseille)
Minimal dominating sets enumeration with FPT-delay parameterized by the (degeneracy and) maximum degree

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

Christophe Paul (Équipe AlGCo)
Linear time modular decomposition algorithm

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.

Laure Morelle (Équipe AlGCo)
An introduction to odd-minors

Odd-minors, which are essentially minors preserving the parity of
cycles, are relatively unknown but would gain to be more famous due to
their possible applications to coloring, parameterized complexity, and
structural graph theory, to cite just a few. In particular,
odd-minor-closed graph classes generalize both minor-closed graph
classes and bipartite graphs. We present here known results and
conjectures related to odd-minors, and revisit a graph width parameter
that we dub bipartite treewidth, that seems closely related to odd-minors.

Timothé Picavet (LaBRI, Bordeaux)
A parameterized approximation scheme for the 2D-Knapsack problem with wide items

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.

Timothé Picavet (LaBRI, Bordeaux)
Locally approximating dominating sets in K_{2,t}-minor-free graphs

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.

Ana Silva (Universidade Federal do Ceará)
Menger-related Problems on Temporal 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).

Dimitrios M. Thilikos (Équipe AlGCo)
Universal Obstructions of Graph Parameters

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 Problem Session ()
Open Problem Session of AlGCo Team

Open problems session of AlGCo-team

Clément Maria (Équipe DataShape, INRIA)
Parameterized complexity in low dimensional topology

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.

Hoang La (Jagiellonian University in Kraków, Poland)
Boolean dimension of boolean lattices

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.

Cléophée Robin (Laboratoire G-Scop, Grenoble, Auvergne-Rhône-Alpes, France)
A Closure Lemma for tough graphs and Hamiltonian degree conditions (14h30)

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

Mathieu Mari (université de Varsovie et IDEAS-NCBR)
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangle

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,
Madhusudhan Reddy and Andreas Wiese.

Hugo Jacob (Équipe AlGCo, LIRMM)
On the parameterized complexity of computing tree-partitions

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
given tree-partition for FPT algorithms. Our simple sketch can be adapted for several regimes within polynomial time and FPT time. Furthermore, we adapt some simple structural results about the tree-partition width of subdivisions, and use them to compare tree-cut width and tree-partition width.

Based on joint work with Hans Bodlaender and Carla Groenland.

Alexandre Talon (École normale supérieure de Lyon | ENS Lyon - Département Informatique)
The complexity of colouring graphs without C4's or stable sets of size 4: a story with a C++ program

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.
As Lozin and Malyshev recall in Vertex coloring of graphs with few obstructions, when the set H contains only graphs with 4 vertices there are only 3 remaining minimal classes of graphs for which the complexity of the colouring problem is still unknown. We study here one of these classes: the class of graphs containing neither cycles of size 4 nor stables of size 4, denoted by, Free{C4, 4K1}.
In (2P2, K4)-Free Graphs are 4-colorable, Gaspers and Huang showed that this class contains only graphs which can be covered by at most 4 cliques. According to the clique covering number, the problem shows different facets: easy if 2-cliques colourable, but harder otherwise.
We present here our partial results concerning the harder case. To tackle it, we use two complementary approaches: one theoretical, dealing with the concepts of clique-width, and one consisting in enumerating and recognising interesting structures using a computer program.
This talk could also mention enumerating graphs being the intersection of rectangles, if the audience wants to know about this.

This is a joint work with Cléophée Robin and Marco Caoduro

Nofar Carmeli (BOREAL joint project-team (LIRMM, Inria, Univ Montpellier, CNRS))
Query answering: tractability beyond acyclicity

Consider the task of enumerating the answers to natural join queries over databases.
Given a join query, it is known that this can be done with ideal time guarantees (linear preprocessing and constant delay) iff the query is alpha-acyclic, under some fine-grained complexity assumptions. In the first part of the talk, we will inspect how the non-acyclic case can be handled, and in particular consider the affect of self-joins and endomorphisms in the query graph on the complexity. In the second part, we will consider more demanding query-answering tasks and see how to extend the requirements from the query structure beyond acyclicity to support these tasks efficiently.

William Lochet (Équipe AlGCo, LIRMM)
Minimum-Membership Geometric Set Cover for unit squares

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.
In this talk, we will focus on the problem where the sets S and R represent geometric objects. This setting was first studied by Erlebach and van Leeuwen in 2008, where they showed NP-hardness for approximating the problem with a ratio less than 2 on unit disks and unit squares. They also gave a 5-approximation algorithm that runs in polynomial time when OPT is bounded (n^O(OPT)) for the case of unit squares. The main goal of the talk will be to present a constant factor approximation algorithm that runs in (truly) polynomial time.

This is based on joint work with S. Bandyapadhyay, S. Saurabh, and J. Xue.

Giannos Stamoulis (Équipe AlGCo, LIRMM)
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate dp$_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the scattered disjoint paths logic, FOL+SDP, where we further consider the atomic predicate $s$-sdp$_k(x_1,y_1,\ldots,x_k,y_k),$ demanding that the disjoint paths are within distance bigger than some fixed value $s$. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus.

Joint work with Petr Golovach and Dimitrios M. Thilikos

Petr A. Golovach (Department of Informatics, University of Bergen, Norway)
Shortest cycles with monotone submodular costs

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

Aliaume Lopez (ENS Paris-Saclay, CNRS, LMF)
Locality and the Łoś–Tarski Theorem in Finite Model Theory

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”.

Noleen Kölher (LMSADE, Paris)
Twin-Width VIII: Delineation and Win-Wins

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

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

Joint work with Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Raul Lopes and Stéphan Thomassé.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Joint work with Christophe Paul

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

joint work with Kshitij Gajjar

Dibyayan Chakraborty (ENS Lyon)
Approximation of isometric path cover

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

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

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

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

Joint work with Antonis Skarlatos.

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

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

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

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

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

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

Joint work with Benjamin Bergougnoux and Jan Dreier.

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

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

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

Joint work with Sebastian Wiederrecht und Raphael Steiner.

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

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

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

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

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

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

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

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

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

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

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

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

Joint work with Bart Jansen

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

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

Joint work with Claire Hilaire.

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

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

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

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

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

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

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

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

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

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

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

Joint work with Peter Rossmanith

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

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

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

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

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

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

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

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

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

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

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

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

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

Joint work with Dimitrios M. Thilikos

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

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

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

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

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

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

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

Joint work with Lokshtanov, Saurabh and Zehavi

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

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

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

Édouard Bonnet (MC2, LIP, ENS Lyon)
Twin-width of matrices and ordered graphs

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Joint work with Olivier Bodini and Noam Zeilberger

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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