Oscar Defrain (LIS, Aix-Marseille Université) Title:Énumération Algorithmique VII. Génération ordonnée ou approche incrémentale 18/11/2024 10h00, salle REU 04.05 (LIS Luminy)
Cet exposé est le septième d’une série d’exposés sur le thème de l’énumération algorithmique où sont présentés différentes techniques, résultats et problèmes ouverts du domaine. Dans cet épisode, on s’intéressera à une approche appelée « génération ordonnée » qui consiste à énumérer toutes les solutions sur des morceaux de plus en plus gros de l’instance jusqu’à obtenir les solutions de l’instance générale. Formalisée en ces termes en 2002, cette approche a depuis connu plus ou moins de succès dans des classes admettant de bonnes décompositions : instances dégénérées, empilées, etc.
Jean-Florent Raymond (LIP, Université de Lyon) Title:A Ramsey-type theorem for traceable graphs, revisited 4/11/2024 14h00, salle REU 04.05 (LIS Luminy)
Consider a graph G with a path P of order n. What conditions force G to also have a long induced path? As complete bipartite graphs have long paths but no long induced paths, a natural restriction is to forbid some fixed complete bipartite graph Ktt as a subgraph. In this case we show that G has an induced path of order (\log \log n)^{1/5-o(1)}. This is an exponential improvement over a result of Galvin, Rival, and Sands (1982) and comes close to a recent upper bound of order O((\log \log n)²).
Pascal Préa (LIS, Aix-Marseille Université) Title:Un algorithme efficace pour reconnaitre les dissimilarités dont tous les chemins de tous les arbres de longueur minimale sont Robinsoniens, partie 2. 14/10/2024 10h00, salle REU 04.05 (LIS Luminy)
Étant donné une dissimilarité d sur un ensemble X, un arbre T=(X,E) est R-compatible avec (X,d) si pour tous x, z dans X et tout y sur le chemin entre x et z, d(x,z)≥ max{d(x,y), d(y,z)}. Si T est compatible avec (X,d), alors T est un arbre de longueur minimale (ALM — MST) de (X,d). Étant donné (X,d) avec |X|=n, nous présenterons dans cet exposé un algorithme en O(n^2) pour vérifier si un ALM donné T est compatible (avec (X,d)) et un algorithme en O(n^3) qui détermine si tous les ALM de (X,d) sont R-compatibles.
Simon Vilmin (LIS, Aix-Marseille Université) Title:Séparation par demi-espaces dans la convexité monophonique 30/09/2024 10h00, salle REU 04.05 (LIS Luminy)
Une convexité sur un univers fini X est une collection de sous-ensembles de X, dits convexes, contenant le vide, X, et fermée par intersection. Cette notion de convexité généralise la convexité classique dans IR^d et capture également de nombreux objets tels que les convexes d'une géométrie convexe, les flats d'un matroïde, les attracteurs d'un réseau booléen, ou encore les modèles d'une CNF de Horn. Nous serons intéressé ici par la grande famille des convexités définies à partir de graphes. Dans une convexité, un convexe H dont le complémentaire X \ H est convexe est appelé un demi-espace. Deux sous-ensembles A et B de X sont alors dits séparables s'il existe une paire de demi-espaces (H, X \ H) telle que A soit inclus dans H et B dans X \ H. A nouveau, cette notion de séparabilité généralise la séparabilité de deux convexes (disjoints) de IR^d, et a été très étudiée d'un point de vue structurel--via des axiomes de séparation--dans les convexités de graphes et les convexités en général. Dans cet exposé on s'intéressera plutôt au problème de décision associé pour la convexité monophonique, c.-à.-d la convexité induite par les chemins sans cordes d'un graphe. Le problème se formule ainsi : étant donnés un graphe G et deux ensembles de sommets A et B, décider de la séparabilité de A et B. Bien que le problème soit NP-complet pour la convexité géodésique--la convexité des plus courts chemins--on montrera qu'il peut être résolu en temps polynomial pour la convexité monophonique.
Pascal Préa (LIS, Aix-Marseille Université) Title:Un algorithme efficace pour reconnaitre les dissimilarités dont tous les chemins de tous les arbres de longueur minimale sont Robinsoniens, partie 1. 16/09/2024 10h00, salle REU 04.05 (LIS Luminy)
Étant donné une dissimilarité d sur un ensemble X, un arbre T=(X,E) est R-compatible avec (X,d) si pour tous x, z dans X et tout y sur le chemin entre x et z, d(x,z)≥ max{d(x,y), d(y,z)}. Si T est compatible avec (X,d), alors T est un arbre de longueur minimale (ALM — MST) de (X,d). Étant donné (X,d) avec |X|=n, nous présenterons dans cet exposé un algorithme en O(n^2) pour vérifier si un ALM donné T est compatible (avec (X,d)) et un algorithme en O(n^3) qui détermine si tous les ALM de (X,d) sont R-compatibles.
Aurélie Lagoutte (GSCOP, Université Grenoble Alpes) Title:Online algorithm for the Canadian Traveler Problem on outerplanar graphs 17/06/2024 14h00, salle REU 04.05 (LIS Luminy)
Given a graph G and two vertices s and t, the Canadian Traveler Problem consists in finding a "short" path between s and t in G, when some unexpected obstacles (for example, snow falls) can block up to k edges, for some input integer k. The status (open or blocked) of each edge is discovered only when walking through one of its extremities, and the traveler has to decide at each step of his walk the next vertex to visit. The goal is to minimise the ratio between the length of the walk from s to t that the traveler actually performs, and the actual distance from s to t he would have traversed knowing the blocked edges in advance. Even though the optimal competitive ratio is 2k + 1 even on unit-weighted planar graphs of treewidth 2, we design a polynomial-time strategy achieving competitive ratio 9 on unit-weighted outerplanar graphs, and this ratio is best possible. Finally, we show that it is not possible to achieve a constant competitive ratio (independent of G and k) on weighted outerplanar graphs.
Oscar Defrain (LIS, Aix-Marseille Université) Title:On the hardness of inclusion-wise minimal separators enumeration 10/06/2024 10h00, salle REU 04.05 (LIS Luminy)
Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedepth computation, the enumeration of inclusion-wise minimal separators plays a crucial role. However and quite surprisingly, the complexity status of this problem has not been settled since it has been posed as an open direction by Kloks and Kratsch in 1998. Recently at the PACE 2020 competition dedicated to treedepth computation, solvers have been circumventing that by listing all minimal a-b separators and filtering out those that are not inclusion-wise minimal, at the cost of efficiency. Naturally, having an efficient algorithm for listing inclusion-wise minimal separators would drastically improve such practical algorithms. In this note, however, we show that no efficient algorithm is to be expected from an output-sensitive perspective, namely, we prove that there is no output-polynomial time algorithm for inclusion-wise minimal separators enumeration unless P = NP.
Iván Rasskin (LIS, Aix-Marseille Université) Title:On the arithmetic and the geometry of regular crystallographic sphere packings and their connection to knot theory 27/05/2024 10h00, salle REU 04.05 (LIS Luminy)
The Apollonian Circle Packing (ACP) is a classic geometric fractal with diverse applications across various domains, particularly in number theory. This is due to its ability to be realized as an integral packing, where the curvatures of all the circles are integers. The ACP is constructed iteratively, beginning with an initial packing whose combinatorial structure is encoded by a tetrahedron. By changing the initial configuration, the ACP can be generalized for any polyhedron. However, not every polyhedron is integral in the sense that it can generate an integral packing. Moreover, in higher dimensions, not every polytope is crystallographic, meaning that it can generate an Apollonian-like sphere packing. In this talk, we will study the integrality and the crystallography of the regular polytopes in any dimension. Furthermore, we will demonstrate how a specific cross-section of a hyperoctahedral crystallographic sphere packing can be utilized as a geometric framework to establish an upper bound on a knot invariant for rational links.
Frédéric Havet (INRIA, Sophia-Antipolis) Title:Inversions in oriented graphs 06/05/2024 10h00, salle REU 04.05 (LIS Luminy)
The inversion of a set X of vertices in an oriented graph consists in reversing the direction of all arcs of the subdigraph induced by X. This generalization of single arc reversal introduced by Belkhechine et al. yields a notion of distance between orientations of a same graph where two orientations are at distance one if and only if there is a set X whose inversion transforms one into the other. First we will discuss the minimum number of inversions required to make an oriented graph acyclic, and in particular a proof of the existence of n-vertex oriented graphs at distance n-o(n) of any acyclic orientation. We also investigate the minimum number of inversions needed to make an oriented graph k-strong, especially in the case of tournaments. Finally, we show various bounds on the maximum distance between two orientations of a same graph. This gives an undirected graph parameter that we show to be tied to several known parameters, including the star chromatic number and acyclic chromatic number. We also prove that two orientations of a same planar graph are at distance at most 12. All these results relied on an algebraic point of view on this problem that allows us to use linear algebra in the field with two elements. This talk on joint papers with Guillaume Aubian, Julien Duron, Florian Horsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud and Quentin Vermande.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Énumération Algorithmique VI. Flipping method. 29/04/2024 10h00, salle REU 04.05 (LIS Luminy)
Cet exposé est le sixième d’une série d’exposés sur le thème de l’énumération algorithmique où sont présentés différentes techniques, résultats et problèmes ouverts du domaine. Dans cet épisode, on s’intéressera à un cas particulier de supergraph method multi-sources qui concerne l’énumération des dominants minimaux dans les graphes. Cette technique, appelée « flipping method » se base sur la génération de dominants minimaux depuis les stables maximaux par échange de sommets ayant pour but de réduire le nombre d’arête.
Jean-Florent Raymond (CNRS, LIP, Lyon) Title:Local certification of geometric graph classes 15/04/2024 14h30, salle REU 04.05 (LIS Luminy)
The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of size Ω(n). This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of Ω(n^{1−δ}) for any δ>0 on the size of the certificates, and an upper bound of O(n log n). The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.
Oscar Defrain (LIS, Aix-Marseille Université) Title:On the enumeration of signatures of XOR-CNF’s 08/04/2024 10h00, salle REU 04.05 (LIS Luminy)
Given a CNF formula φ with clauses C1,…,Cm over a set of variables V, a truth assignment a : V→{0,1} generates a binary sequence σ(a)=(C1(a),…,Cm(a)), called a signature of φ, where Ci(a)=1 if clause Ci evaluates to 1 under assignment a, and Ci(a)=0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.
Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In PODS 2017 Carmeli et al. proved that all minimal chordal completions or equivalently all proper tree decompositions of a graph can be listed in incremental polynomial time using exponential space. The total running time of their algorithm is quadratic in the number of solutions and the existence of an algorithm whose complexity depends only linearly on the number of solutions remained open. We close this question by providing a polynomial delay algorithm to solve this problem which, moreover, uses polynomial space. Our algorithm relies on Proximity Search, a framework recently introduced by Conte et al. (STOC 2019) which has been shown powerful to obtain polynomial delay algorithms, but generally requires exponential space. In order to obtain a polynomial space algorithm for our problem, we introduce a new general method called canonical path reconstruction to design polynomial delay and polynomial space algorithms based on proximity search.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Énumération algorithmique V. Proximity search. 19/02/2024 10h00, salle REU 04.05 (LIS Luminy)
Cet exposé est le cinquième d’une série d’exposés sur le thème de l’énumération algorithmique où sont présentés différentes techniques, résultats et problèmes ouverts du domaine. Dans cet épisode, on s’intéressera à une surcouche subtile du « supergraph method » qui a été proposée récemment sous le nom de « proximity search » et qui a permis de résoudre un grand nombre de problèmes ouverts. Seront entre autres à l’honneur l’énumération des sous-graphes maximaux k-dégénérés d’un graphe quelconque.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Énumération algorithmique IV. Supergraph method. 05/02/2024 10h00, salle REU 04.05 (LIS Luminy)
Cet exposé est le quatrième d’une série d’exposés sur le thème de l’énumération algorithmique où sont présentés différentes techniques, résultats et problèmes ouverts dans ce domaine relativement récent. Dans cet épisode, on s’intéressera à une technique d’énumération généralement appelée « supergraph method » qui repose sur le parcours d’un graphe des solutions bien choisi. On s’intéressera en particulier à l’énumération des sous-graphes vérifiant une propriété héréditaire, des arbres couvrant d’un graphe, ou encore à l’énumération des bases d’un matroid.
Yann Strozecki (DAVID, Université de Versailles Saint-Quentin) Title:Geometric Amortization of Enumeration Algorithms 22/01/2024 13h00, salle REU 04.05 (LIS Luminy)
We introduce the technique of geometric amortization for enumeration algorithms. This technique can be used to make the delay of enumeration algorithms more regular without much overhead on the space it uses. More precisely, we are interested in enumeration algorithms having incremental linear delay, that is, algorithms enumerating a set A of size K such that for every t≤K, it outputs at least t solutions in time O(tp), where p is the incremental delay of the algorithm. While it is folklore that one can transform such an algorithm into an algorithm with delay O(p), the naive transformation may blow the space exponentially. We show that, using geometric amortization, such an algorithm can be transformed into an algorithm with delay O(plogK) and O(slogK) space, where s is the space used by the original algorithm. We apply geometric amortization to show that one can trade the delay of flashlight search algorithms for their average delay modulo a factor of O(logK). We illustrate how this tradeoff may be advantageous for the enumeration of solutions of DNF formulas.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Sparse graphs without long induced paths 08/01/2024 10h00, salle REU 04.05 (LIS Luminy)
Graphs of bounded degeneracy are known to contain induced paths of order Ω(log log n) when they contain a path of order n, as proved by Nešetřil and Ossona de Mendez (2012). In 2016 Esperet, Lemoine, and Maffray conjectured that this bound could be improved to Ω((log n)^c) for some constant c>0 depending on the degeneracy. We disprove this conjecture by constructing, for arbitrarily large values of n, a graph that is 2-degenerate, has a path of order n, and where all induced paths have order O((log log n)^2).
Christopher Thraves (Universidad de Concepción, Chili) Title:Separating path systems in trees 27/11/2023 10h00, salle REU 04.05 (LIS Luminy)
For a graph $G$, an edge-separating (resp. vertex-separating) path system of $G$ is a family of paths in $G$ such that for any pair of edges $e_1, e_2$ (resp. pair of vertices $v_1, v_2$) of $G$ there is at least one path in the family that contains one of $e_1$ and $e_2$ (resp. $v_1$ and $v_2$) but not the other. In this talk, we will see how to determine the size of a minimum edge-separating path system of an arbitrary tree $T$ as a function of its number of leaves and degree-two vertices. Also, we will present bounds for the size of a minimal vertex-separating path system for trees, which we show to be tight in many cases. Finally, we will give similar results for a variation of the definition, where we require the path system to separate edges and vertices simultaneously.
Patrice Bertrand (Ceremade, Université Paris Dauphine) Title:Convexités d’intervalles et classifications multiniveaux 20/11/2023 10h00, salle REU 04.05 (LIS Luminy)
Les hiérarchies d’ensembles et la plupart des modèles de classification multiniveau peuvent être caractérisés en termes de convexité d’intervalles. Dans cet exposé, nous introduisons un cadre axiomatique général permettant d’identifier des propriétés de convexité respectivement de la hiérarchie d’Apresjan, de la hiérarchie faible de Bandelt et Dress et de la hiérarchie du lien simple qui sont chacune associées à une dissimilarité arbitraire. En particulier, nous déterminons une filtration respectivement de la hiérarchie du lien simple, de la hiérarchie faible de Bandelt et Dress et de toute convexité d’intervalle contenant la hiérarchie d’Apresjan. Finalement, nous présentons quelques contributions potentielles de cette approche à l’utilisation des méthodes de classification hiérarchique.
Jérémie Chalopin (LIS, Aix-Marseille Université) Title:Reconstruire un complexe cubique CAT(0) à partir de sa frontière 06/11/2023 10h00, salle REU 04.05 (LIS Luminy)
Dans cet exposé, on montrera comment on peut reconstruire un complexe cubique CAT(0) X à partir des distances entre les sommets de sa frontière (les distances étant calculés dans le 1-squelette de X). Cela résout une conjecture récente de Haslegrave, Scott, Tamitegama et Tan (2023). Pour établir ce résultat, on utilise la correspondance entre les complexes cubiques CAT(0) et les graphes médians, ainsi que le fait que les graphes médians admettent un ordre de démontage par coins (on expliquera tout ça pendant l'exposé). Travail réalisé avec Victor Chepoi.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Enumerating minimal solution sets for metric graph problems. 23/10/2023 10h00, salle REU 04.05 (LIS Luminy)
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.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Énumération Algorithmique III. Difficultés de l’énumération et réductions polynomiales. 09/10/2023 10h00, salle REU 04.05 (LIS Luminy)
Cet exposé est le troisième d’une série d’exposés sur le thème de l’énumération algorithmique où seront présentés différentes techniques, résultats et problèmes ouverts dans ce domaine relativement récent. Dans cet épisode, on s’intéressera aux réductions polynomiales entre problèmes d’énumération, et à la preuve de leur difficulté qui se traduit bien souvent par « il n’existe pas d’algorithme total-polynomial pour Π à moins que P = NP » et qui de fait exclut la possibilité d’algorithmes à délai polynomial ou incrémental polynomial. On s’intéressera en particulier aux problèmes d’énumération des indépendants maximaux donnés par un oracle, à l’énumération des modèles maximaux d’une formule de Horn, et à la place importante que s’est faite la dualisation des fonctions monotones Booléennes en énumération.
Guyslain Naves (LIS, Aix-Marseille Université) Title:Plongement dans L1 de métriques planaires préservant les distances entre sommets d’une même face. 25/09/2023 10h00, salle REU 04.05 (LIS Luminy)
Le théorème d'Okamura-Seymour affirme que les métriques induites par un graphe planaire sur les sommets de sa face extérieure sont plongeables dans L1. Une conjecture fameuse est que toute métrique induite par un graphe planaire est plongeable dans L1 avec une distortion constante. Je présenterai un article récent de Nikhil Kumar (FOCS 2022) qui étend le théorème d'Okamura-Seymour et constitue une avancée vers cette conjecture : tout graphe planaire G est plongeable dans L1, de sorte que pour toute face F, la métrique induite sur cette face subit une distortion constante.
Victor Chepoi (LIS, Aix-Marseille Université) Title:Separation axioms $S_3$ and $S_4$ in convexity spaces and graphs 11/09/2023 10h00, salle REU 04.05 (LIS Luminy)
In the talk, we will present old and new results about the separation by halfspaces of pairs of disjoint convex sets ($S_4$) and of points and convex sets ($S_3$).
Feodor Dragan (Kent State University, USA) Title:$\alpha_i$-Metric Graphs: Radius, Diameter and all Eccentricities 26/06/2023 10h00, salle REU 04.05 (LIS Luminy)
We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called $\alpha_i$-metric ($i\in \mathcal{N}$) if it satisfies the following $\alpha_i$-metric property for every vertices $u,w,v$ and $x$: if a shortest path between $u$ and $w$ and a shortest path between $x$ and $v$ share a terminal edge $vw$, then $d(u,x)\geq d(u,v) + d(v,x)-i$. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a ``near-shortest'' path with defect at most $i$. It is known that $\alpha_0$-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are $\alpha_i$-metric for $i=1$ and $i=2$, respectively. We show that an additive $O(i)$-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an $\alpha_i$-metric graph can be computed in total linear time. Our strongest results are obtained for $\alpha_1$-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called $(\alpha_1,\Delta)$-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least $7$). The latter answers a question raised in (Dragan, {\it IPL}, 2020). Our algorithms follow from new results on centers and metric intervals of $\alpha_i$-metric graphs. In particular, we prove that the diameter of the center is at most $3i+2$ (at most $3$, if $i=1$). The latter partly answers a question raised in (Yushmanov \& Chepoi, {\it Mathematical Problems in Cybernetics}, 1991). This is a joint work with Guillaume Ducoffe.
Alixel Bagnis (LIS, Aix-Marseille Université) Title:Énumération des signatures d’une CNF. 19/06/2023 10h00, salle REU 04.05 (LIS Luminy)
Si Φ = C1 ∧ C2 ∧ … ∧ Cm est une CNF et 𝓪 est un assignement, alors la signature de 𝓪 sur Φ est le mot binaire s où le i-ème bit est à 1 si et seulement si 𝓪 évalue Ci à 1. On appelle un mot binaire de taille m une signature de Φ s’il existe un assignement dont il est la signature sur Φ. La signature vient traduire le fait qu’il existe un assignement qui satisfait telles et telles clauses et ne satisfait pas telles ou telles clauses. En particulier Φ est satisfiable ssi 111…1 est une signature. De ce fait, décider si s est la signature d'une 3-CNF est NP-complet. Malgré tout et de façon assez étonnante, Berczi et al. montrent que l'énumération de toutes les signatures d'une CNF quelconque reste possible en temps incrémental polynomial. L'objet de cet exposé est de présenter le problème, l'algorithme de Berczi et al., et de distinguer quelques questions ouvertes qui ont été l'objet de ce stage.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Minimal dominating sets enumeration with FPT-delay parameterized by the degeneracy and maximum degree 12/06/2023 10h00, salle REU 04.05 (LIS Luminy)
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, for an appropriate definition of degeneracy. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether, even for a more restrictive notion of degeneracy, this XP-delay algorithm parameterized by d could be improved to an FPT-delay algorithm parameterized by d and the maximum degree ∆, i.e., an algorithm with delay f(d, ∆) · n^{O(1)} for some computable function f. We answer this question in the affirmative whenever the hypergraph corresponds to the closed neighborhoods of a given graph, i.e., we show that the intimately related problem of enumerating minimal dominating sets in graphs can be solved with FPT-delay parameterized by the degeneracy and the maximum degree.
Simon Vilmin (LORIA, Université de Lorraine) Title:Enumération des modèles maximaux d’une formule de Horn. 05/06/2023 10h00, salle de séminaire du 3ème (FRUMAM, St-Charles)
L'énumération des modèles maximaux d'une formule de Horn est un problème difficile qui apparaît implicitement dans plusieurs domaines de l'informatique, allant du data mining à la logique modale. En outre, il généralise la dualisation des fonctions monotones booléennes (ou dualisation des hypergraphes) et se rapporte au problème de dualisation dans les treillis codés par des bases d’implications. Dans cet exposé, je présenterai le problème et quelques résultats connus à son sujet. En général, le problème ne peut être résolu en temps total polynomial à moins que P = NP, ce qui suggère l'étude de cas particuliers. Je m'intéresserai au cas où les clauses négatives de la formule ont taille deux, qui fait écho au codage d'un graphe médian au moyen d'un ordre partiel et d'un graphe de conflit. En tirant parti du lien entre formules de Horn et treillis, j'utiliserai le nombre de Carathéodory (que l'on retrouve notamment en optimisation combinatoire) et la dualisation des hypergraphes pour donner des classes de formules où le problème peut être résolu en temps total (quasi-)polynomial. Je mentionnerai aussi des classes de treillis où le problème est déjà plus dur que la dualisation des hypergraphes, même si les clauses négatives sont de tailles deux.
Guyslain Naves (LIS, Aix-Marseille Université) Title:Répartiteur dans les réseaux de convoyeurs 15/05/2023 10h00, salle REU 04.05 (LIS Luminy)
Lors d'un précédent exposé, j'avais introduit les réseaux de convoyeurs, modélisant le transport de matériaux sur des tapis roulants et utilisant des appareils nommés splitters et permettant d'uniformiser les charges entre deux tapis. Dans cet exposé, après un rappel des notions, je montrerais comment construire des réseaux permettant d'uniformiser les charges d'un nombre arbitraire de tapis avec aussi peu de splitters que possible. Je prouverai des bornes inférieures sur le nombre de splitters nécessaires, et selon le temps aborderai quelques résultats supplémentaires de complexité. Il n'est pas nécessaire d'avoir vu l'exposé précédent pour suivre celui-ci.
Mathieu Mari (MIMUW, Université de Varsovie) Title:A (2+ɛ)-approximation algorithm for maximum independent set of rectangles 17/04/2023 10h00, salle REU 04.05 (LIS Luminy)
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.
Colin Geniet (ENS Lyon) Title:Twin-width of groups and bounded degree graphs 12/04/2023 10h30, salle REU 04.05 (LIS Luminy)
Twin-width is a graph invariant introduced by Bonnet, Kim, Thomassé, and Watrigant, with notable applications in logic, FPT algorithms, and graph coloring. When considering graphs of bounded degree, finiteness of twin-width is stable under quasi-isometries, and thus it defines an invariant of the Cayley graphs of a group. For a group G, having finite twin-width is equivalent to admitting a total order for which the self-action by product avoids some permutations as patterns, which makes twin-width a far reaching generalisation of the notion of orderable groups. Several well-known classes of groups have finite twin-width: abelian groups, solvable groups, groups with polynomial growth, and hyperbolic groups. On the other hand, the class of all cubic graphs is known to have unbounded twin-width by a counting arguments: for any k, there are only n!c^n graphs of twin-width k on vertices {1,...,n} for some constant c (we say that it is a _small_ class of graphs), which is asymptotically less than the number of cubic graphs. Using an embedding theorem of Osajda, we adapt this construction to prove that there are groups with infinite twin-width. The Cayley graphs of such groups induce classes of graphs which are small but have unbounded twin-width, answering a question from previous works. Unfortunately, because these constructions are enumerative and probabilistic, it is essentially impossible to understand the resulting group. Finding an explicit construction for graphs with bounded degree (or groups) and unbounded twin-width remains a major open problem.
Clément Dallard (LIFO, Université d’Orléans) Title:Introduction to tree-independence number 03/04/2023 10h00, salle REU 04.05 (LIS Luminy)
Tree decompositions are a common and useful data structure for designing dynamic programming algorithms for graph problems. In order to obtain efficient algorithms, one looks for a tree decomposition of the input graph that minimizes some measure on the subgraphs induced by the bags. For instance, when this measure is the number of vertices, we obtain the well-known notion of treewidth. In this talk, the considered measure is the independence number. The independence number of a tree decomposition of a graph G is the smallest integer k such that each bag induces a subgraph with independence number at most k. The tree-independence number of G is defined as the minimum independence number over all tree decompositions of G. Given a tree decomposition with bounded independence number, the Maximum Weight Independent Set and several related NP-hard problems can be solved in polynomial time. We will discuss how to compute tree decompositions with bounded independence number efficiently (when they exist), the algorithmic use of such tree decompositions, and the strong relationship with the notion of (tw,ω)-boundedness.
Benjamin Bergougnoux (MIMUW, Université de Varsovie) Title:A logic-based algorithmic meta-theorem for mim-width 27/03/2023 10h00, salle REU 05.37 (LIS Luminy)
We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (𝖠&𝖢 𝖣𝖭 for short) which extends existential 𝖬𝖲𝖮𝟣 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 𝖠&𝖢 𝖣𝖭 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 (𝖤𝖳𝖧) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the 𝖤𝖳𝖧 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-𝖭𝖯-hard when parameterized by mim-width plus formula length.
Jean-Florent Raymond (CNRS, Université Clermont Auvergne) Title:A lower bound for constant-size local certification 20/03/2023 10h00, salle REU 04.05 (LIS Luminy)
Given a graph property, a local certification is a labeling that allows to locally check that the property is satisfied. The quality of a certification is measured by the size of its labels: the smaller, the better. This can be seen as a measure of the locality of a property (where properties that can be certified with "small" labels are considered more local than the others). An active line of research is to identify the optimal label size for a given graph property. It turns out that properties can be classified into three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored, at least on the lower bound side. In this talk I will present the first non-trivial lower bound for this low regime: k-colorabilty cannot be certified with just one bit.
Laurent Viennot (INRIA, Paris) Title:Temporalisation of walks/edges in a graph 13/03/2023 10h00, salle REU 04.05 (LIS Luminy)
In a temporal graph, each edge appears and can be traversed at specific points in time. In such a graph, temporal reachability of one node from another is naturally captured by the existence of a temporal path where edges appear in chronological order. Inspired by the optimisation of bus/metro/tramway schedules in a public transport network, we consider the problem of turning a collection of walks (called trips) in a directed graph into a temporal graph by assigning a starting time to each trip so as to maximise the reachability among pairs of nodes. Each trip represents the trajectory of a vehicle and its edges must be scheduled one right after another. Setting a starting time to the trip thus forces the appearing time of all its edges. We call such a starting time assignment a trip temporalisation. We obtain several results about the complexity of maximising reachability via trip temporalisation. Among them, we show that maximising reachability via trip temporalisation is hard to approximate within a factor $\sqrt{n}/12$ in an $n$-vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalisation connecting them. On the positive side, we show that there must exist a trip temporalisation connecting a constant fraction of all pairs if we additionally assume symmetry, that is, when the collection of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order. We will also discuss the basic problem of assigning times to the edges of a directed graphs so as to maximise temporal reachability.
Valentin Bartier (GSCOP, Université de Grenoble) Title:Reconfiguration d’ensembles indépendants dans les graphes peu denses. 06/03/2023 10h00, salle REU 04.05 (LIS Luminy)
Le problème de reconfiguration d’ensembles indépendants appartient au domaine plus large des problèmes de reconfiguration combinatoire. Il se formule de la manière suivante : étant donné une collection de jetons placés sur les sommets d’un ensemble indépendant d’un graphe, est-il possible de déplacer un à un ces jetons vers un autre ensemble indépendant cible, de telle sorte que deux jetons ne soient jamais voisins tout au long de la transformation ? Après une introduction générale sur la reconfiguration combinatoire et sur le problème de reconfiguration d’ensembles indépendants, nous nous concentrerons sur la variante du « Token Sliding ». Dans cette variante, une étape de la transformation consiste à déplacer un jeton d’un sommet vers un sommet voisin. Nous nous intéresserons plus particulièrement à la complexité paramétrée de ce problème dans des classes de graphes peu denses et aux nouveaux outils que nous avons récemment développé pour l’élaboration d’algorithmes FPT.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Énumération algorithmique II. Énumération des cliques maximales. 27/02/2023 10h00, salle REU 04.05 (LIS Luminy)
Cet exposé est le second d’une série d’exposés sur le thème de l’énumération algorithmique où seront présentés différentes techniques, résultats et problèmes ouverts dans ce domaine relativement récent. Dans cet épisode, on présentera un algorithme à délai polynomial pour l'énumération des cliques maximales d'un graphe, un problème qui fut au centre de l'attention dans les années 70/80 et dont la résolution par Tsukiyama et al. inspira de nombreuses techniques d'énumération.
Owen Rouillé (INRIA, Paris) Title:Experimenting in mathematics: examples of data generation and visualisation. 13/02/2023 10h00, salle REU 04.05 (LIS Luminy)
Mathematics include many complex objects which are difficult to understand. In particular, intuition is crucial in teaching and research, allowing to state and prove conjectures. Building this intuition requires looking at and analysing many examples. Computers are very important tools at our disposal: they allow to generate and analyse large quantities of data, and visualise patterns that would be difficult to draw by hand. However, using them is not straightforward, and implementation raises many new questions, among which the encoding and the performances for instances. The talk is dedicated to the use of computers to help with mathematics. First, I will present part of the work I did during my PhD concerning the computation of two topological invariants for 3-manifolds (Turaev--Viro invariants and hyperbolic volume). These projects illustrate the use of computers in mathematics in a domain where the computations can be difficult and the datasets very large. Then, I will present the main project of my postdoc: the computation and the representation of limit sets in S^3, with a focus on triangular groups.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Énumération algorithmique I. Prémisses de l’énumération, backtrack et systèmes indépendants. 06/02/2023 10h00, salle REU 04.05 (LIS Luminy)
Cet exposé est le premier d’une série d’exposés sur le thème de l’énumération algorithmique où seront présentés différentes techniques, résultats et problèmes ouverts dans ce domaine relativement récent. Dans cet épisode, on parlera dans un premier temps des prémisses de l'énumération et des différentes complexités que l’on souhaite garantir en énumération. Ces notions seront ensuite illustrées par la la présentation d’une première technique d'énumération : le backtrack search, ses variantes et limitations. Seront évoqués entre autres le problème des 8 dames, l’énumération de clusters ou encore l’énumération des solutions (maximales ou non) au problème du sac à dos.
Given a graph, the objective of ISOMETRIC PATH COVER (IPC) is to select minimum number of isometric (i.e. shortest) paths to cover all vertices. In this talk, we shall see how a simple breadth first search based algorithm provides constant factor approximation algorithms for IPC on many graph classes including graphs with bounded hyperbolicity, (long) [theta, prism, pyramid]-free graphs and outer-string graphs. On the negative side IPC remains NP-hard on chordal graphs. For analysis of our approximation algorithm, we propose a new parameter called "Isometric path antichain cover number (ipacc)" of graphs which remains bounded on all the above graph classes. We wonder if this parameter has other applications.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Chemins évitables dans les graphes 09/01/2023 10h00, salle REU 04.05 (LIS Luminy)
Un graphe est triangulé si chacun de ses cycles induits est un triangle. Un résultat classique de Dirac énonce que tout graphe triangulé admet un sommet simplicial, i.e., un sommet dont le voisinage est une clique. Une façon de généraliser ce résultat passe par la notion de chemin évitable. Un chemin P dans un graphe G est évitable s'il est induit et si tout chemin induit xPy---où x et y sont des sommets de G---est contenu dans un cycle induit de G. Notons que dans les graphes triangulés, un chemin de longueur 1 qui est évitable est exactement un sommet simplicial. En 2019, Beisegel, Chudnovsky, Gurvich, Milanič et Servatius conjecturent que pour tout entier positif k, tout graphe contenant un chemin induit à k sommets contient également un chemin évitable à k sommets. Cette conjecture n'était établie que pour k=1 et k=2. On donne une preuve simple de la conjecture pour tout k, qui implique également un résultat de Chvátal, Rusu et Sritharan de 2002 qui supposait des restrictions sur la taille des cycles dans le graphe.
An extremity is a vertex such that the removal of its closed neighbourhood does not increase the number of connected components. Let Ext_α be the class of all connected graphs whose quotient graph obtained from modular decomposition contains no more than α pairwise nonadjacent extremities. Our main contributions are as follows. First, we prove that the diameter of every m-edge graph in Ext_α can be computed in deterministic O(α^3m^{3/2}) time. We then improve the runtime to O(α^3m) for bipartite graphs, to O(α^5m) for triangle-free graphs, O(α^3∆m) for graphs with maximum degree ∆, and more generally to linear for all graphs with bounded clique-number. Furthermore, we can compute an additive +1-approximation of all vertex eccentricities in deterministic O(α^2m) time. This is in sharp contrast with general m-edge graphs for which, under the Strong Exponential Time Hypothesis (SETH), one cannot compute the diameter in O(m^{2−\eps}) time for any \eps > 0. As important special cases of our main result, we derive an O(m^{3/2})-time algorithm for exact diameter computation within dominating pair graphs of diameter at least six, and an O(k^3m^{3/2})-time algorithm for this problem on graphs of asteroidal number at most k. Both results extend prior works on exact and approximate diameter computation within AT-free graphs. To the best of our knowledge, this is also the first deterministic subquadratic-time algorithm for computing the diameter within the subclasses of: chordal graphs of bounded leafage (generalizing the interval graphs), k-moplex graphs and k-polygon graphs (generalizing the permutation graphs) for any fixed k. We end up presenting an improved algorithm for chordal graphs of bounded asteroidal number, and a partial extension of our results to the larger class of all graphs with a dominating target of bounded cardinality. Our time upper bounds in the paper are shown to be essentially optimal under plausible complexity assumptions. Our approach is purely combinatorial, that differs from most prior recent works in this area which have relied on geometric primitives such as Voronoi diagrams or range queries. On our way, we uncover interesting connections between the diameter problem, Lexicographic Breadth-First Search, graph extremities and the asteroidal number.
Luigi Santocanale (LIS, Aix-Marseille Université) Title:Des treillis de permutations (signés) au graphes threshold 05/12/2022 10h00, salle REU 04.05 (LIS Luminy)
Dans cet exposé je rappellerai comment on peut définir, pour les graphes de Coxeter, une structure d'ordre à partir de leur graphe de Cayley. Si le groupe est fini, cet ordre est un treillis. Pour les types A,B et D, ces groupes/treillis sont le groupes symétriques (permutations), des permutations signés, permutations signés paires (c.-à-d., avec un nombre pair de signes négatifs) respectivement.La recherche d'une caractérisation explicite de l'ordre pour les permutations signés paires nous amène à découvrir une représentations de ces objets par des chemins, par laquelle il devient facile d’établir preuves bijectives d'identités concertants les nombres d'Euler pour les type B et D.La même représentation mène à découvrir une relation intime entre permutations signés (paires) et graphes threshold, et à trouver preuves bijectives de formules enumeratives pour cette classes de graphes.
Marco Caoduro (INP, Université de Grenoble) Title:Hitting and Packing Squares 10/10/2022 10h00, salle REU 04.05 (LIS Luminy)
Let S be a finite family of (not necessarily axis-parallel) squares in the plane. The hitting number of S, denoted by τ (S), is the minimum number of points needed to hit all the squares in S, and the packing number of S, denoted by ν(S), is the maximum number of pairwise disjoint squares in S. Both problems are NP-hard even in the restricted case of axis-parallel unit squares. It is quite surprising that the most natural bounds between packing and hitting numbers are wide open also for some of the simplest geometric objects. We aim to decrease this gap for not necessarily axis-parallel squares by presenting the first bounds for the τ /ν ratio. Our upper bounds are 6 for unit squares and 10 for squares of varying sizes, while the worst ratios we can provide with examples are 3 and 4, respectively. These new bounds necessitate a mixture of novel and classical techniques of possibly extendable use. For comparison, in the axis-parallel case, the supremum of the considered ratio is in the interval [ 3/2, 2 ] for unit squares and [ 3/2, 4 ] for arbitrary squares. During the talk, we will give ideas and intuitions behind the most important proofs and show how our approach extends to families of rectangles with a bounded aspect ratio. Also, the degeneracy argument used in the proofs will allow deducing similar bounds for the ratio between the chromatic and clique numbers.
Étant donné un ensemble de segments dans le plan, on se donne pour objectif de raccourcir leur longueur totale via une suite de «décroisements». Un décroisement remplace deux segments sécants par deux autres en réutilisant les mêmes extrémités. Quelle est alors la complexité du problème ? En 1980, on démontre qu’il y a au plus n^3 décroisements dans une telle suite. Cette borne supérieure reste la meilleur connue, alors que l’on conjecture n^2.
Jean-Christophe Godin (Institut de Mathématiques de Toulon) Title:On List Coloring with Separation of the Complete Graph and Set-System intersections 12/09/2022 10h00, salle REU 04.05 (LIS Luminy)
We consider the following list coloring with separation problem: Given a graph G and integers a, b, find the largest integer c such that for any list assignment L of G with |L(v)| = a for any vertex v and |L(u) ∩ L(v)| ≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u) ⊂ L(u) and |φ(v)| = b for any vertex u and φ(u) ∩ φ(v) = ∅ for any edge uv. Such a value of c is called the separation number of (G, a, b). Using a special partition of a set of lists for which we obtain an improved version of Poincaré’s crible, we determine the separation number of the complete graph Kn for some values of a, b and n, and prove bounds for the remaining values.
Simon Vilmin (LIRIS, Université de Lyon) Title:Traduction entre meet-irréductibles et bases d’implications qui codent un treillis. Pt. II 30/05/2022 10h00, salle REU 04.05 (LIS Luminy)
Il est connu qu’un treillis peut se coder (parfois de façon très compacte) par l’ensemble de ses éléments meet-irréductibles, ou bien par une base d’implications. En quelque sorte, la première représentation décrit ce qui fait partie du treillis, quand la deuxième décrit ce qui n’en fait pas partie. Ces deux représentations étant d’utilité algorithmique incomparable, le problème (très largement ouvert) de leur traduction (passer de l’une à l’autre) a suscité un intérêt grandissant ces 30 dernières années. Dans cet exposé, je présenterai le problème (sa formulation, son intérêt, ses liens dans les hypergraphes et la logique de Horn) puis donnerai quelques algorithmes permettant sa résolution dans des classes (trop) restreintes.
Oscar Defrain (LIS, Aix-Marseille Université) Title:Traduction entre meet-irréductibles et bases d’implications qui codent un treillis. Pt. I 02/05/2022 10h00, salle REU 04.05 (LIS Luminy)
Il est connu qu’un treillis peut se coder (parfois de façon très compacte) par l’ensemble de ses éléments meet-irréductibles, ou bien par une base d’implications. En quelque sorte, la première représentation décrit ce qui fait partie du treillis, quand la deuxième décrit ce qui n’en fait pas partie. Ces deux représentations étant d’utilité algorithmique incomparable, le problème (très largement ouvert) de leur traduction (passer de l’une à l’autre) a suscité un intérêt grandissant ces 30 dernières années. Dans cet exposé, je présenterai le problème (sa formulation, son intérêt, ses liens dans les hypergraphes et la logique de Horn) puis donnerai quelques algorithmes permettant sa résolution dans des classes (trop) restreintes.
An induced path is a path, while the reverse is not true in general. Can we however guarantee that a graph has a "long" induced path if it has a "large" path, for a suitable definition of "long" and "large"? In this talk I will discuss this question in minor-closed classes, with the following results: 1) If a graph of pathwidth less than k has a path of order n, then it has an induced path of order at least 1/3 * n^{1/k}. This is an exponential improvement over the previous bounds. 2) If a graph of treewidth less than k has a path of order n, then it has an induced path of order at least 1/4 * (log n)^{1/k}. - If a graph from a fixed topological minor-closed class has a path of order n, then it has an induced path of order at least (log n)^d, for some constant d depending on the class.
Guyslain Naves & Pascal Préa (LIS, Aix-Marseille Université) Title:Reconnaissance en temps optimal des dissimilarités de Robinson 28/03/2022 10h00, salle REU 04.05 (LIS Luminy)
Un espace de dissimilarité $(X,d)$ est un espace de Robinson s'il existe un ordre total $<$ sur $X$ tel que pour tous $x < y < z$, $d(x,z) \geq \max \{ d(x,y), d(y,z) \}$. Le problème de reconnaissance d'un espace de Robinson s'apparente à un tri en dimension 2. Un mmodule est un ensemble $M \subseteq X$ tel que pour tous $x,y \in M$, $z \notin M$, $d(z,x) = d(z,y)$. Dans ce travail, nous étudions la structure des mmodules d'un espace de Robinson, et en déduisons un algorithme de reconnaissance des espaces de Robinson en temps optimal $O(n^2)$ (où $n := |X|$), qui comparativement aux précédents algorithmes connus est simple à implémenter et efficace.
Guyslain Naves (LIS, Aix-Marseille Université) Title:Réseaux de convoyeurs équilibrants 29/11/2021 10h00, salle REU 04.05 (LIS Luminy)
Un réseau de convoyeurs est un réseau de tapis roulants de capacité uniforme connectés par des répartiteurs. Un répartiteur relie deux convoyeurs entrants à deux convoyeurs sortants en essayant d'équilibrer le débit entre ses deux entrées et ses deux sorties. Je présenterai d'abord des algorithmes polynomiaux inspirés des algorithmes de flot maximum pour calculer les débits effectifs des convoyeurs d'un tel réseau en fonction des débits des entrées et des sorties du réseau. Puis je donnerai des constructions de réseaux permettant d'uniformiser les charges d'un nombre arbitraire de convoyeurs et utilisant un nombre minimum de répartiteurs.
Le fait que la matrice des vecteurs caractéristiques des boules de rayon R d'un arbre soit totalement balancée permet d'obtenir un algorithme simple et efficace pour le problème de R-domination pondéré dans les arbres. Dans cet exposé, nous montrerons que l'algorithme d'approximation facteur 2 pour le problème de la multicoupe dans les arbres peut-être également vu comme une conséquence du fait que la matrice des vecteurs caractéristiques des chemins d'un arbre est la somme de deux matrices totalement balancées.Par la suite, nous montrerons qu'une relaxation de cette propriété est vérifiée par la matrice des voisinages de plus courts chemins dans un graphe delta-hyperbolique. Cela nous permettra de décrire un algorithme efficace qui calcule un transversal des (R+O(delta))-voisinages de plus courts chemins d'un graphe delta-hyperbolique dont le poids est au plus deux fois celui d'un transversal de poids minimum des R-voisinages de ces chemins.
Manon Philibert (LIS, Aix-Marseille Université) Title:Sample compression schemes. Pt. III 08/11/2021 10h00, salle REU 04.05 (LIS Luminy)
In a series of seminars, together with my colleagues we will present some known results and some new our results about sample compression schemes for concept classes. The sample compression conjecture asserts that any concept class of VC-dimension d admits a compression scheme of size O(d).
Guyslain Naves (LIS, Aix-Marseille Université) Title:Algorithmes efficaces pour les problèmes de connexité. Pt. II 18/10/2021 10h00, salle REU 5.37 (LIS Luminy)
Le principal résultat de l'article est de montrer qu'il est possible d'échantillonner les arêtes d'un graphe G pondéré selon une distribution de probabilités calculables en temps quasi-linéaire, de sorte que le graphe pondéré obtenu H possède O(n log n) arêtes et les valeurs des coupes dans G sont proches à un facteur (1+epsilon) de celles des coupes correspondantes de H. Cet algorithme est un ingrédient fondamental pour de nombreux algorithmes en temps quasi-linéaire liés à la connexité des graphes.
Victor Chepoi (LIS, Aix-Marseille Université) Title:Sample compression schemes. Pt. II 11/10/2022 10h00, salle REU 04.05 (LIS Luminy)
In a series of seminars, together with my colleagues we will present some known results and some new our results about sample compression schemes for concept classes. The sample compression conjecture asserts that any concept class of VC-dimension d admits a compression scheme of size O(d).
Victor Chepoi (LIS, Aix-Marseille Université) Title:Sample compression schemes. Pt. I 27/09/2022 10h00, salle REU 04.05 (LIS Luminy)
In a series of seminars, together with my colleagues we will present some known results and some new our results about sample compression schemes for concept classes. The sample compression conjecture asserts that any concept class of VC-dimension d admits a compression scheme of size O(d).
Guyslain Naves (LIS, Aix-Marseille Université) Title:Algorithmes efficaces pour les problèmes de connexité. Pt. I 13/09/2021 10h00, salle REU 5.37 (LIS Luminy)
Récemment, plusieurs résultats impressionnants d'algorithmique pour des problèmes de complexité sont parus. En particulier, un algorithme linéaire déterministe pour trouver une coupe minimum dans un graphe (Jason Li), et un algorithme pour all-pair-max-flow plus rapide que les meilleures algorithmes pour all-pair-shortest-path dans les graphes non pondérés (Abboud, Krauthgamer, Trabelsi), ce qui peut sembler contre-intuitif au regard des complexités de max-flow et shortest-path. J'ai l'intention de vous présenter ces deux algorithmes et probablement d'autres, mais comme ils reposent sur d'autres résultats intermédiaires, nous allons commencer plus modestement. Pour ce premier séminaire, nous étudierons donc un algorithme d'éparsification d'Ibaraki et Nagamochi, pour trouver un sous-graphe préservant toutes les coupes de poids au plus k d'un graphe en temps linéaire, et si le temps le permet, un algorithme de Khandekar, S. Rao et U. Vazirani, d'approximation de la coupe la plus éparse en O(n \sqrt(n) polylog(n)).
Mathieu Mari (MIMUW, Université de Varsovie) Title:Approximating maximum integral multiflows on bounded genus graphs 05/07/2021 10h00, en ligne
In this talk, I will present a constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.
Ugo Giocanti (LIS, Aix-Marseille Université) Title:Graphs with convex balls and groups acting on them 28/06/2021 10h00, salle REU 04.05 (LIS Luminy)
Graphs with convex balls (called for short CB-graphs) were first studied separately in the eighties by Chepoi and Soltan and by Farber and Jamison. They generalize systolic and weakly systolic graphs, and enjoy some analogous properties to those of weakly modular and Helly graphs. I will first characterize CB-graphs as those graphs satisfying two metric properties, called the Interval Neighborhood Condition and the Triangle Pentagon Condition. Then I will define a notion of clique paths in CB-graphs that can be locally characterized, and prove that the associated paths enjoy the 2-sided fellow traveller property. Thanks to a result of Swiatkowski, I will show that it implies that CB-groups are biautomatic. I will mention other results we obtained about CB-graphs, as a local to global characterisation of them, a Helly theorem that they enjoy and the fact that their squares are dismantlable. According to the time that will remain, I will sketch some proofs of these results.
Oscar Defrain (MIMUW, Université de Varsovie) Title:Sur le problème de dualisation dans les graphes, hypergraphes et treillis 15/03/2021 10h00, en ligne
On s'intéresse au problème de dualisation des fonctions monotones Booléennes, ainsi qu'à ses généralisations, à travers les différentes formes qu'il prend dans les graphes, hypergraphes, et treillis: énumération des dominants minimaux, énumération des transversaux minimaux, dualisation dans les treillis, et traductions entre les représentations d'un treillis. En particulier, on donnera un algorithme pour énumérer les dominants minimaux dans les graphes sans clique de taille fixée, en un temps qui est polynomial en la taille du graphe, plus le nombre de solutions. L'existence d'un tel algorithme dans les graphes généraux est l'une des questions les plus importantes en énumération. On explorera ensuite les différentes généralisations naturelles de ce problème dans les treillis, et les questions ouvertes qui en découlent. Parmi celles-ci, quelques-unes géométriques.
