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 E3.23 bât. 4 ou sur ZOOM - https://www.lirmm.fr/algco/GT/zoom - (en distanciel).

()

Evangelos Protopapas (Équipe AlGCo)
Universal Obstructions of Graph Parameters

We establish a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $\leq$ on graphs.
At the center of this framework lies the concept of a $\leq$-parametric graph: a non $\leq$-decreasing sequence ${G} = \langle {G}_{t} \rangle_{t \in \mathbb{N}}$ of graphs indexed by non-negative integers.
Parametric graphs allow us to define combinatorial objects that capture the approximate behaviour of graph parameters.
A finite set $\mathfrak{G}$ of $\leq$-parametric graphs is a $\leq$-universal obstruction for a parameter $\mathsf{p}$ if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every $k \in \mathbb{N}$ and every graph $G$, 1) if $\mathsf{p}(G) \leq k$, then for every ${G} \in \mathfrak{G},$ ${G}_{f(k)} \not\leq G$, and 2) if for every ${G} \in \mathfrak{G},$ ${G}_{k} \not\leq G$, then $\mathsf{p}(G) \leq f(k).$
To solidify our point of view, we identify sufficient order-theoretic conditions that guarantee the existence of universal obstructions and in this case we examine algorithmic implications on the existence of fixed-parameter tractable algorithms.

Our parametric framework has further implications related to finite obstruction characterizations of properties of graph classes.
A $\leq$-class property is defined as any set of $\leq$-closed graph classes that is closed under set inclusion.
By combining our parametric framework with established results from order theory, we derive a precise order-theoretic characterization that ensures $\leq$-class properties can be described in terms of the exclusion of a finite set of $\leq$-parametric graphs.

As a proof of concept we apply our viewpoint to the study of Erdős-Pósa dualities for the minor relation.
We say that a pair $({H},{G})$ of minor-closed classes is an {Erdős-Pósa pair} (EP-pair for short) if there exists a function $f \colon \mathbb{N} \to \mathbb{N}$ such that for every $k \in \mathbb{N}$ and every graph $G \in {G},$ either $G$ has $k$ pairwise vertex-disjoint subgraphs which do not belong to ${H},$ or there exists a set $S\subseteq V(G)$ of size at most $f(k)$ for which $G - S \in {H}.$
For every minor-closed class ${H}$ we define the minor-class property $\mathbb{EP}_{H}$ as the set of all minor-closed classes ${G}$ for which $(H, G)$ is an EP-pair.

We prove that for every minor-closed class ${H}$ there exists a {finite} set of grid-like minor-parametric graphs $\mathfrak{G}_{H}$ such that a minor-closed class ${G}$ belongs to $\mathbb{EP}_{H}$ if and only if for every ${G} \in \mathfrak{G}_{H},$ ${G}$ does not contain ${G}_{k},$ for some $k \in \mathbb{N}.$
In particular, we provide an explicit description for $\mathfrak{G}_{H}$ for every ${H}$ and give a constructive upper bound on its size.
Moreover, each ${G}_{k}$ admits a half-integral packing, i.e., $k$ copies of some graph in ${H}$ where no vertex is used more than twice.
This implies a complete delineation of the half-integrality threshold of the Erdős-Pósa property for minors, and as a corollary, we obtain a constructive proof of Thomas' conjecture on the half-integral Erdős-Pósa property for minors which was recently confirmed by Liu.
Our results are algorithmic.
For every minor-closed graph class ${H},$ we obtain an algorithm that, given a graph on $n$ vertices and $k \in \mathbb{N},$ outputs either a half-integral packing of $k$ copies of some graph in ${H}$ or a set of at most $2^{k^{O(1)}}$ vertices whose deletion yields a graph in ${H}$ in time $O_{k}(n^4 \log n).$
As a consequence of our results we obtain minor-universal obstructions for the graph parameters ${H}$-treewidth, elimination distance to ${H},$ and apex number to ${H},$ for every minor-closed class ${H}.$

Dimitrios Thilikos (AlGCo, LIRMM)
Deciding properties of minor-closed graph classes in polynomial time: a case study

We initiate a case study for the problem of deciding graph class properties, based on their finite descriptions. In particular, we deal with properties of minor-closed graph classes where such a description is their finite obstruction set. The question on whether there is a polynomial-time algorithm for such problems is related to the conjecture that $ω^2$-WQO of graphs with respect to the minor relation, which is a major open problem in Order Theory. We present a series of instantiations of the above problem where such algorithms exist and can be constructed.

Corentin Lunel (Inria, Montpellier (équipe Datashape))
Some knot theory results inspired by graph theory

The first problem we address concerns the decidability of a knot invariant. The genus of a knot is a classical knot invariant: it is
the minimal genus of an embedded orientable surface in the 3-dimensional space admitting the knot as its boundary. It is now fairly
well understood from a computational perspective. On the contrary, no algorithm is known for its 4 dimensional variants, both in
the smooth and in the topological locally flat category. We investigate a class of knots and links called Hopf arborescent links, which
are obtained as the boundaries of surfaces constructed by iterated plumbings of Hopf bands. We show that for such links, computing the
genus defects, which measure how much the four-dimensional genera differ from the classical genus, is decidable. Our proof is
non-constructive and is obtained by proving that a containment relation on surfaces associated to Hopf arborescent links forms a
well-quasi-order.

The second problem we tackle is motivated by the existence of efficient algorithms to compute many knot invariants and properties on
diagrams of low treewidth. It was recently proved that there exist knots which do not admit any diagram of low treewidth, and the proof
relied on intricate low-dimensional topology techniques. We initiate here a thorough investigation of tree decompositions of knot
diagrams (or more generally, diagrams of spatial graphs) using ideas from structural graph theory. We define an obstruction on spatial
embeddings that forbids low treewidth diagrams, and we prove that it is optimal with respect to a related width invariant. We then show
the existence of this obstruction whenever an embedding into a surface with high compression-representativity exists, which is the case
for torus knots. Thus, we provide a new and self-contained proof that those do not admit diagrams of low treewidth.

David Saulpic (CNRS, IRIF)
Making Old Things New: A Unified Algorithm for Differentially Private Clustering

As a staple of data analysis and unsupervised learning, the
problem of private clustering has been widely studied under various
privacy models. Centralized differential privacy is the first of them,
and the problem has also been studied for the local and the shuffle
variation. In each case, the goal is to design an algorithm that
computes privately a clustering, with the smallest possible error. The
study of each variation gave rise to new algorithms: the landscape of
private clustering algorithms is therefore quite intricate.
With Max Dupré la Tour and Monika Henzinger, we showed that a
20-year-old greedy algorithm can be slightly modified to work for any
of these models. This provides a unified picture: while matching
almost all previously known results, it allows us to improve some of
them and extend it to some recent privacy models.

In this talk, I will present this old greedy algorithm, and try to
explain its advantages over other approaches for clustering. I will
then introduce the notion of differential privacy and its variants,
and show how to use the greedy algorithm for private clustering.

Oscar Defrain (Université Aix-Marseille)
Enumerating minimal solution sets for metric graph problems

Problems from metric graph theory such as Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had a strong impact on the field of parameterized complexity by being the first problems in NP to admit double-exponential lower bounds in the treewidth, and even in the vertex cover number for the latter. We initiate the study of enumerating minimal solution sets for these problems and show that they are also of great interest in enumeration. More specifically, we show that enumerating minimal resolving sets in graphs and minimal geodetic sets in split graphs are equivalent to hypergraph dualization, arguably one of the most important open problems in algorithmic enumeration. This provides two new natural examples to a question that emerged in different works this last decade: for which vertex (or edge) set graph property Π is the enumeration of minimal (or maximal) subsets satisfying Π equivalent to hypergraph dualization? As only very few properties are known to fit within this context-namely, properties related to minimal domination-our results make significant progress in characterizing such properties, and provide new angles of approach for tackling hypergraph dualization. In a second step, we consider cases where our reductions do not apply, namely graphs with no long induced paths, and show these cases to be mainly tractable.

Aliaume Lopez (Université de Varsovie)
Well-quasi-ordered classes of bounded (linear) clique-width: an automata based approach

A class of graphs is (labelled) well-quasi-ordered (WQO) whenever any infinite subset of this class contains two (labelled) graphs G and H such that G is an induced subgraph of H respecting the labeling. We provide an algorithm to decide whether a class of finite graphs that has bounded linear clique width is labelled WQO, where the class is given by an MSO-transduction from finite words. This study leverages tools from automata theory, and as a byproduct we answer positively to a conjecture of Pouzet: for such classes of graphs, being WQO using finitely many labels is equivalent to being WQO with infinite sets of labels. We also provide an automata based characterization of earlier results of Daligault, Rao and Thomassé [10.1007/s11083-010-9174-0, Theorem 3] by encoding the models into trees ordered with the gap embedding relation of Dershowitz and Tzameret. This work is available on arxiv: https://arxiv.org/abs/2405.10894.

Gordon Royle (University of Western Australia)
Cubic graphs with no eigenvalues in the open interval (-1,1)

Spectral graph theory is the study of the relationship between the
graphical properties of a graph and the spectral properties (i.e.,
eigenvalues and eigenvectors) of various matrices associated with that
graph, most commonly the adjacency matrix. The spectrum of the
adjacency matrix of a cubic graph (i.e., one where each vertex has
three neighbours) on n vertices is a set of n real numbers lying in
the interval [-3,3] which determines a surprising amount of
information about the graph. A spectral gap set X is an open subset of
(-3,3) with the property that there are an infinite number of cubic
graphs whose spectrum is disjoint from X. For example, the interval
(-3,-2) is a spectral gap set because the infinite family of cubic
line graphs has no eigenvalues in (-3,-2), and in fact the list of all
cubic graphs whose spectrum avoids (-3,-2) is known. The fact that
(-1,1) is a spectral gap set for cubic graphs has been shown at least
twice previously, with two different (but closely related) infinite
families of cubic graphs. In this talk, I describe some recent work,
joint with Krystal Guo, where we give an exact characterisation of the
cubic graphs whose spectrum avoids (-1,1). This allows us to deduce
that (-1,1) is a maximal gap set, thereby answering a question of
Kollar and Sarnak.

Guilherme Gomes (AlGCo)
Matching (Multi)Cut: Algorithms, Complexity, and Enumeration

A matching cut of a graph is a partition of its vertex set in two such that no vertex has more than one neighbor across the cut. The Matching Cut problem asks if a graph has a matching cut. This problem, and its generalization d-cut, has drawn considerable attention of the algorithms and complexity community in the last decade, becoming a canonical example for parameterized enumeration algorithms and kernelization. In this paper, we introduce and study a generalization of Matching Cut, which we have named Matching Multicut: can we partition the vertex set of a graph in at least $\ell$ parts such that no vertex has more than one neighbor outside its part?

We investigate this question in several settings.

We start by showing that, contrary to Matching Cut, it is NP-hard on cubic graphs but that, when $\ell$ is a parameter, it admits a quasi-linear kernel. We also show an $\mathcal{O}(\ell^{\frac{n}{2}})$ time exact exponential algorithm for general graphs and a $2^{\mathcal{O}(t\log t)}n^{\mathcal{O}(1)}$ time algorithm for graphs of treewidth at most $t$.

We then turn our attention to parameterized enumeration aspects of matching multicuts. First, we generalize the quadratic kernel of Golovach et. al for Enum Matching Cut parameterized by vertex cover, then use it to design a quadratic kernel for Enum Matching (Multi)cut parameterized by vertex-deletion distance to co-cluster. Our final contributions are on the vertex-deletion distance to cluster parameterization, where we show an FPT-delay algorithm for Enum Matching Multicut but that no polynomial kernel exists unless NP $\subseteq$ coNP/poly; we highlight that we have no such lower bound for Enum Matching Cut and consider it our main open question.