Séminaires 2024 - 2025

Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en salle H208 ou H202 ou C101. Les responsables sont Moritz Mühlenthaler et Alantha Newman, n'hésitez pas à les contacter.

Pendant la pandémie nous avons organisé un séminaire virtuel (conjointement avec Lyon et Clermont-Ferrand), le Séminaire virtuel de théorie des graphes et combinatoire en Rhône-Alpes et Auvergne.

Jeudi 15 mai 2025 (14h30) : Dibyayan Chakraborty (University of Leeds) : On (Strong) isometric path complexity of graphs.

(Strong) isometric path complexity is a graph invariant that aims to capture how arbitrary isometric paths (i.e. shortest path between its end vertices) of a finite graph can be viewed as union of small number of "rooted" isometric paths. This parameter can be computed in polynomial time. In this talk, first we will show that (strong) isometric path complexity is bounded for some interesting graph classes, including hyperbolic graphs, $K_{2,t}$-induced minor-free graphs, U_t-asymptotic minor-free graphs, etc. Here, U_t refers to a path on $t$ vertices along with a universal vertex. Then, we will show some graph operations that preserves (strong) isometric path complexity. We will also mention some algorithmic applications (if time permits).

This talk is based on the following.
1. Dibyayan Chakraborty, Florent Foucaud: Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations. (2025).
2. Dibyayan Chakraborty : K2,3 -induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two. (2025).
3. Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, Yann Vaxès: Isometric Path Complexity of Graphs. (MFCS 2023).
Jeudi 24 avril 2025 (14h30) : Romain Bourneuf (LaBRi, Bordeaux & LIP, Lyon) : A Dense Neighborhood Lemma with Applications to Domination and Chromatic Number

In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of R^N such that for each v in V the ball B(v,1) intersects V on at least delta |V| points, then for every epsilon >0, the points of V can be covered with f(delta,epsilon) balls B(v,1+epsilon) with v in V. DNL also applies to other metric spaces and to abstract set systems, where elements are compared pairwise with respect to (near) disjointness. In its strongest form, DNL provides an epsilon-clustering with size exponential in 1/epsilon, which amounts to a Regularity Lemma with 0/1 densities of some trigraph. I will discuss the notion of VC-dimension, and explain how to generalize it to trigraphs to obtain statements such as DNL. I will then discuss some applications of DNL to the chromatic number of dense triangle-free graphs, and to domination in tournaments of bounded fractional chromatic number.
Jeudi 17 avril 2025 (14h30) : Srikanth Srinivasan (University of Copenhagen, Danemark) : Algebraic Circuit Complexity and Polynomial Identity Testing

This talk will be a gentle introduction to algebraic circuit complexity and its connection to algorithmic problems such as Perfect Matching and Exact Matching, via the Polynomial Identity Testing (PIT) problem. We will discuss how to prove impossibility results (or "lower bounds") in the setting of algebraic circuits and how that is connected to deterministic algorithms for PIT.
Jeudi 10 avril 2025 (14h30) : Guyslain Naves (LIS, Université Aix-Marseille) : The steady-states of splitter networks

We introduce splitter networks, which abstract the behavior of conveyor belts found in the video game Factorio. Based on this definition, we show how to compute the steady-state of a splitter network. Then, leveraging insights from the players community, we provide multiple designs of splitter networks capable of load-balancing among several conveyor belts, and prove that any load-balancing network on n belts must have Ω(n log n) nodes. Incidentally, we establish connections between splitter networks and various concepts including flow algorithms, flows with equality constraints, rotor-routers, Markov chains and the Knuth-Yao theorem about sampling over rational distributions using a fair coin.

Joint work with Bastien Gastaldi and Basile Couëtoux.
Jeudi 3 avril 2025 (14h30) : Bruno Grenet (LJK, UGA) : Time- and space-efficient polynomial computations

In computer algebra, efficient polynomial computations usually consist of two parts: fast polynomial multiplication algorithms (from Karatsuba's seminal algorithm to FFT-based algorithms) and efficient reductions of many tasks to polynomial multiplications. This provides quasi-linear-time algorithms for polynomial multiplication, division, multipoint evaluation, interpolation, GCD computation, … In terms of space complexity, fast multiplication algorithms as well as the reductions to polynomial multiplication usually require at least a linear amount of extra space. On the other hand, there are so-called naive algorithms of quadratic complexity which only require constant space.
In this talk, I will describe recent results on the design of time- and space-efficient algorithms for polynomial computations. The goal is to provide fine-grained time-space complexity upper bounds for these problems. This requires a discussion of the models of space complexity for computing functions. Many open questions remain in this area, either on the practical side of designing better algorithms or on the theoretical side of understanding the relationships between the different space complexity models.

This is based on joint works with Pascal Giorgi (U. Montpellier), Daniel S. Roche (USNA, Annapolis) and Jean-Guillaume Dumas (U. Grenoble-Alpes).
Jeudi 27 mars 2025 (14h30) : Lucas De Meyer (LIRIS, Univ. Lyon 1) : An algorithmic Vizing’s theorem: toward efficient edge-coloring sampling with an optimal number of colors

The problem of sampling edge-colorings of graphs with maximum degree ∆ has received considerable attention and efficient algorithms are available when the number of colors is large enough with respect to ∆. Vizing’s theorem guarantees the existence of a (∆ + 1)-edge-coloring, raising the natural question of how to efficiently sample such edge-colorings. In this paper, we take an initial step toward addressing this question. Building on the approach of Dotan, Linial, and Peled, we analyze a randomized algorithm for generating random proper (∆ + 1)-edge-colorings, which in particular provides an algorithmic interpretation of Vizing’s theorem. The idea is to start from an arbitrary non-proper edge-coloring with the desired number of colors and at each step, recolor one edge uniformly at random provided it does not increase the number of conflicting edges (a potential function will count the number of pairs of adjacent edges of the same color). We show that the algorithm almost surely produces a proper (∆ + 1)-edge-coloring and propose several conjectures regarding its efficiency and the uniformity of the sampled colorings.
Jeudi 20 mars 2025 (14h30) : Pierre Hoppenot (G-SCOP) : Identifying a graph via its reconfiguration graph

Given a graph G, its k-recolouring graph has a vertex for each k-colouring[1] of G, and edges between pairs of colourings that differ on one vertex only. Recently, Hogan et al.[2] proved that G can be recovered from its k-recolouring graph, provided k is large enough (quadratic in the number of vertices of G). We improve this bound by showing that k=chi(G)+1 colours suffice, and that this is best possible. We then extend this result to the case of Kempe changes, adding edges between colourings where a bicoloured connected component of G got its colours swapped. Finally, we investigate the case of independent set reconfiguration and prove that only in a few trivial cases a graph can be recovered from its reconfiguration graph. [1] For us, a k-colouring is a function from V to {1, ..., k} but it does not need to be surjective (and it cannot be when k is too big). [2] Emma Hogan, Alex Scott, Youri Tamitegama, and Jane Tan. A note on graphs of k-colourings. 2024. arXiv: 2402.04237 [math.CO].
Jeudi 13 mars 2025 (14h30) : Alex Talon (G-SCOP) : Colour the edges of K_{n,n} with green and purple. The vertices can be partitioned into 4 monochromatic cycles.

We consider here simple graphs, and colourings of their edges with two colours. We want to partition the vertices of such a graph into the minimum number of monochromatic cycles. Here a single vertex and a single edge are considered as cycles as well. We wonder, whatever the graph and its green-and-purple edge colouring may be, how many cycles do we need in the worst case? When the graph we want to decompose is a clique, Bessy and Thomassé proved in 2010 that two monochromatic cycles are enough, henceforth confirming a conjecture Lehel made in 1970. We investigated the class of balanced complete bipartite graphs (K_{n,n}). If the colouring is "split", then three monchromatic cycles (or even two in some cases) suffice to partition the vertices of a K_{n,n}. We proved that whatever the colouring may be, 4 cycles always suffice for K_{n,n}. Our proof is not constructive: after establishing a few preliminary results about about the structure of the colouring, we assume that such a partition does not exist in so far as deducing more structure on the edge colouring. The framework of the proof is an induction on the size of the graph, involving a case study.
Jeudi 27 février 2025 (14h30) : Robert Hickingbotham (LIP, ENS de Lyon) : Coarse Graph Theory, Quasi-Isometry, and Tree-Decompositions

Coarse graph theory is an emerging research direction that aims to describe the global structure of graphs by ignoring their local structure. In this talk, I will present an overview of this area, highlighting both recent positive and negative developments. A key focus of this talk will be the notion of quasi-isometry and conditions under which graphs are quasi-isometric to graphs with bounded treewidth.

This talk is based on some recent joint works with Rutger Campbell, Maria Chudnowsky, James Davies, Marc Distel, Meike Hatzel, Freddie Illingworth, and Rose McCarty.
Jeudi 20 février 2025 (15h00) : Pierre Bergé (LIMOS, Université Clermont Auvergne) : Computing the diameter efficiently : the case of median graphs

A longstanding and challenging question in algorithmics is the computation of distances in graphs, in particular of the diameter and all eccentricities. A first approach for tackling these problems consists in launching a BFS from each vertex of the input graph: this allows to retrieve all distances in time O(mn), where n (resp. m) is the number of vertices (resp. edges). Unless SETH fails, on sparse graphs, the diameter cannot be approximated within a factor of 3/2 in subquadratic time, which makes multiple BFS a straightforward but efficient method in general. During the last decade, many subquadratic-time algorithms were proposed for the computation of diameter/eccentricities on well-known families of sparse graphs, for example on bounded-treewidth graphs (Abboud et al., 2016) but also on planar (Cabello, 2018). Certain of these results even highlight exact algorithms running in quasilinear time, i.e. linear time if we neglect poly-logarithmic factors. We present our exact quasilinear-time algorithm dedicated to median graphs for these problems. Median graphs arise in phylogenetics (representation of mitochondrial DNA), geometric group theory (1-skeletons of CAT(0) cube complexes) and logic (model for solutions of 2-SAT).
Jeudi 13 février 2025 (14h30) : Aurélie Lagoutte (G-SCOP) : Online algorithm for the Canadian Traveler Problem on outerplanar graphs

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 competitive ratio better than log k / log log k on weighted outerplanar graphs. The upper bound for this case remains open.
Jeudi 30 janvier 2024 (14h30) : Niloufar Fuladi (Équipe Gamble, LORIA, Nancy) : Universal families of arcs and curves on surfaces

In this talk, I am interested in the size of a family of curves Γ on a surface with the property that for each type of pants decomposition of the surface there exists a homeomorphism sending it to a subset of the curves in Γ. The study of such universal families of curves is motivated by questions on graph embeddings, joint crossing numbers and finding an elusive center of moduli space. I will discuss the case of surfaces without punctures, where we establish an exponential upper bound and a superlinear lower bound on the minimum size of this family of curves with this universal property. I will explain the background and context and no prior knowledge in topology or surfaces is needed.

This is joint work with Arnaud de Mesmay and Hugo Parlier.
Mardi 28 janvier 2024 (14h30) : Anna Gujgiczer (Budapest University of Technology and Economics) : Widely colorable graphs and their multichromatic numbers

An s-wide coloring of a graph is a proper coloring where not just the color classes, but the first, second, ..., (s − 1)th neighborhoods of any color class are also independent sets. Those graphs that admit an optimal s-wide coloring turned out to play a key role in constructing counterexamples to Hedetniemi’s conjecture. In some of these counterexamples knowing the multichromatic number of these graphs became a relevant question.

This talk is mainly based on a joint work with Gabor Simonyi, where we answer this question.
Jeudi 16 janvier 2025 (14h30) : Penny Haxell (University of Waterloo, Canada) : The Integrality Gap for the Santa Claus Problem

In the Max-min Allocation Problem, a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players is maximized. In the restricted variant, also known as the "Santa Claus problem", each resource (``toy'') has an intrinsic positive value, and each player (``child'') covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching. Bezakova and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP of Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs. Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of 3.808 for the general problem to 3.534. We also address the well-studied restricted version in which resources can take only two values, and improve the integrality gap in most cases.
Jeudi 19 décembre 2024 (14h30) : Cléophée Robin (IRIF, Université Paris Cité) : Clique-covering co-bridge-free prismatic graphs

A graph G is prismatic if for every triangle T of G, every vertex of G that is not in T, has exactly one neighbor in T. The complement of a prismatic graph is called antiprismatic. The complexity of the coloring problem when restricted to prismatic graphs is unknown. Chudnovsky and Seymour gave a full structural description of prismatic graphs. They divided the class in two subclasses : the orientable prismatic graphs and the non-orientable prismatic graphs. Preissman, Robin and Trotignon gave an algorithm to solve the clique problem in non-orientable prismatic graphs in polynomial time. We show this algorithm can also be used for prismatic graphs with no 2K_1 + C_4 (co-bridge), whether they are orientable or not. To achieve this, we show that this class of graphs admits a bounded number of disjoint triangles through a cautious analysis of their structure.

This is joint work with Eileen Robinson (Université libre de Bruxelles).
Jeudi 12 décembre 2024 (14h30) : Vincent Cohen-Addad (Google Research) : Sensitivity Sampling for Coreset-Based Data Selection

The scale of modern machine learning models and data has made data selection a central problem. In this talk, we focus on the problem of finding the best representative subset of a dataset to train a machine learning model. We provide a new data selection approach based on 𝑘-means clustering and sensitivity sampling. Assuming embedding representation of the data and that the model loss is Hölder continuous with respect to these embeddings, we prove that our new approach allows to select a set of ``typical'' 1/𝜖2 elements whose average loss corresponds to the average loss of the whole dataset, up to a multiplicative (1±𝜖) factor and an additive 𝜖𝜆Φ𝑘, where Φ𝑘 represents the 𝑘-means cost for the input data and 𝜆 is the Hölder constant. We furthermore demonstrate the performance and scalability of our approach on fine-tuning foundation models and show that it outperforms state-of-the-art methods. We also show that our sampling strategy can be used to define new sampling scores for regression, leading to a new active learning strategy that is comparatively simpler and faster than previous ones like leverage score.
Jeudi 5 décembre 2024 (15h45) : Imre Bárány (Alfréd Rényi Mathematical Institute, Budapest, Hongrie) : A matrix version of the Steinitz lemma

The Steinitz lemma, a classic from 1913, states that a_1,...,a_n, a sequence of vectors in R^d with \sum_{i=1}^n a_i=0, can be rearranged so that every partial sum of the rearranged sequence has norm at most 2d\max |a_i|. It is an important result with several applications. I plan to mention a few. In the matrix version of the Steinitz lemma A is a k times n matrix with entries a_i^j \in \R^d whose sum is the origin. Oertel, Paat, Weismantel have proved recently that there is a rearrangement of row j of A (for every j) such that the sum of the entries in the first m columns of the rearranged matrix has norm at most 40d^5\max |a_i^j| (for every m). We improve this bound to (4d-2)\max |a_i^j|.
Jeudi 5 décembre 2024 (14h30) : Gérard Cornuéjols (Carnegie-Mellon University, USA) : The Replication Conjecture

Abstract: Analogous to perfection in antiblocking theory is the notion of "the packing property" in blocking theory. A key insight on perfect graphs is the famous replication lemma proved by Laci Lovasz in 1972. In 1993, Michele Conforti and I proposed an analogous replication conjecture when the packing property holds. This conjecture is still open. This talk covers some recent developments related to the replication conjecture.

These results are joint with Ahmad Abdi.
Lundi 2 décembre 2024 (14h30) : Bertrand Guenin (University of Waterloo, Canada) : Bridging the gap between Linear and Integer Programming.

Informally, an Integer Program is obtained from a Linear Program by adding the condition that some variables be restricted to be integer. What kind of other restrictions lead to interesting classes of optimization problems? One such class of problems is obtained by restricting the variables in a Linear Program to be dyadic rationals, i.e. rationals where the denominator is a power of two. These problems borrow features from both Linear Programming and Integer Programming. Notably, they can be solved in polynomial time, but optimal solutions may have large support.There is a rich body of work investigating which Linear Programs are guaranteed to have integer solutions. We study which Linear Programs are guaranteed to have dyadic solutions. This is motivated by a 1975 conjecture by Paul Seymour on ideal clutters, that has implications for matchings in graphs, and for directed cuts in digraphs. We also show that this theory has some surprising implications for combinatorial optimization as it leads to a geometric characterization of Total Dual Integrality for non-degenerate instances.
Jeudi 28 novembre 2024 (14h30) : Ahmad Abdi (London School of Economics and Political Science, UK) : Strong orientation of a connected graph for a crossing family (Part II)

Given a connected graph G=(V,E) and a crossing family C over ground set V such that |δ(U)|≥2 for every U∈C, we prove there exists a strong orientation of G for C, i.e., an orientation of G such that each set in C has at least one outgoing and at least one incoming arc. This implies the main conjecture in Chudnovsky et al. (Disjoint dijoins. Journal of Combinatorial Theory, Series B, 120:18--35, 2016).

Joint work with Mahsa Dalirrooyfard and Meike Neuwohner.
Jeudi 21 novembre 2024 (14h30) : Meike Neuwohner (London School of Economics and Political Science, UK) : A characterization of unimodular hypergraphs with disjoint hyperedges

Grossman et al. show that the subdeterminants of the incidence matrix of a graph can be characterized using the graph’s odd cycle packing number. In particular, a graph’s incidence matrix is totally unimodular if and only if the graph is bipartite. We extend the characterization of total unimodularity to disjoint hypergraphs, i.e., hypergraphs whose hyperedges of size at least four are pairwise disjoint. The class of disjoint hypergraphs interpolates between the class of graphs and the class of hy- pergraphs, which correspond to arbitrary {0, 1}-matrices. We prove that total unimodularity for disjoint hypergraphs is equivalent to forbidding both odd cycles and a structure we call an “odd tree house”. Our result extends to disjoint directed hypergraphs, i.e., those whose incidence ma- trices allow for {0, ±1}-entries. As a corollary, we resolve a conjecture on almost totally unimodular matrices, formulated by Padberg (1988) and Cornuéjols & Zuluaga (2000), in the special case where columns with at least four non-zero elements have pairwise disjoint supports.

Joint work with Marco Caoduro and Joseph Paat.
Jeudi 7 novembre 2024 (14h30) : Ahmad Abdi (London School of Economics and Political Science, UK) : Strongly connected orientations and integer lattices (Part I)

Let D=(V,A) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in {x : x_a = i} for any a in A, i in {0,1}. We prove under a mild necessary condition that F \cap {0,1}^A contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs.
Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say tau, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number p >= 2, a p-adic packing of dijoins of value tau and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by F \cap {0,1}^A, where F is the face of P satisfying x(delta^+(U)) = 1 for every minimum dicut delta^+(U).

Based on joint work with Gérard Cornuéjols, Siyue Liu, and Olha Silina.
Jeudi 24 octobre 2024 (14h30) : Alantha Newman (CNRS, G-SCOP) : Recent progress on correlation clustering

In the correlation clustering problem, we are given a complete graph with each edge labeled as + (similar) or - (dissimilar). The goal is to find a clustering (a partition) of the vertices that minimizes the number of dissimilar intracluster edges and the number of similar intercluster edges. Until recently, the best known approximation guarantee was 2.06, based on a modification of the natural LP-based pivot algorithm. We now know how to go below 1.5 using various new tools and insights. In this talk, we will give an overview of these recent developments and discuss some of the open questions.

Based on joint work with Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li and Lucas Vogl.
Jeudi 17 octobre 2024 (14h30) : Louis Esperet (CNRS, G-SCOP) : The clustered Hadwiger conjecture

We prove that every K_h-minor-free graph has an (h-1)-coloring in which every monochromatic component has size bounded by some function of h. The number of colors is optimal, and this proves a conjecture of Edwards, Kang, Kim, Oum and Seymour (2015). The proof of our result heavily relies on 2 recent technical ingredients: the Product Structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood, and a clustered coloring lemma for K_{s,t}-subgraph-free graphs of bounded treewidth by Liu and Wood.

This is joint work with V. Dujmović, P. Morin, and D. Wood.
Jeudi 10 octobre 2024 (14h30) : Rémi Coulon (CNRS, Université de Bourgogne) : Croissance dans les graphes de Cayley des groupes de type fini

Étant donné un groupe G engendré par une partie finie S, on y associe naturellement un graphe homogène, appelé graphe de Cayley, sur lequel on peut lire la table de multiplication du groupe. Naturellement, la géométrie de ce graphe nous informe sur la structure algébrique du groupe. Dans cet exposé on illustrera ce phénomène au travers de la notion de "croissance". L'idée est d'étudier le comportement asymptotique lorsque r tend vers l'infini du cardinal d'une boule de rayon r. Par le biais d'exemples variés on présentera les différents phénomènes qui peuvent apparaître, ainsi que divers problèmes ouverts sur le sujet.
Jeudi 19 septembre 2024 (14h30) : Nicolas Trotignon (LIP, Lyon) : A tamed family of triangle-free graphs with unbounded chromatic number

We construct a hereditary class of triangle-free graphs with unbounded chromatic number, in which every graph on at least three vertices either contains a pair of non-adjacent twins or has an edgeless vertex cutset of size at most two. This answers in the negative a question of Chudnovsky, Penev, Scott and the speaker. These graphs are structurally simple in several ways, in particular regarding their twinwidth. Also, we show how to obtain such graphs with arbitrarily large odd girth.

This is joint work with Édouard Bonnet, Romain Bourneuf, Julien Duron, Colin Geniet and Stéphan Thomassé.
Vendredi 13 septembre 2024 (11h00) : Felix Hommelsheim (Université de Bremen) : Two-Edge Connectivity via Pac-Man Gluing

We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph G, compute a connected subgraph H of G with the minimum number of edges such that H is spanning, i.e., V(H) = V(G), and H is 2-edge-connected, i.e., H remains connected upon the deletion of any single edge, if such an H exists. The 2-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time (5/4+epsilon)-approximation for the problem for an arbitrarily small epssilon>0, improving the previous best approximation ratio of 13/10+epsilon. Our improvement is based on two main innovations: First, we reduce solving the problem on general graphs to solving it on structured graphs with high vertex connectivity. This high vertex connectivity ensures the existence of a 4-matching across any bipartition of the vertex set with at least 10 vertices in each part. Second, we exploit this property in a later gluing step, where isolated 2-edge-connected components need to be merged without adding too many edges. Using the 4-matching property, we can repeatedly glue a huge component (containing at least 10 vertices) to other components. This step is reminiscent of the Pac-Man game, where a Pac-Man (a huge component) consumes all the dots (other components) as it moves through a maze. These two innovations lead to a significantly simpler algorithm and analysis for the gluing step compared to the previous best approximation algorithm, which required a long and tedious case analysis.
Vendredi 13 septembre 2024 (10h00) : Jan van den Heuvel (London School of Economics & Political Science) : Partial Colourings (aka "Timetabling with not Enough Time")

Suppose you have a graph G for which you know the vertices can be properly coloured with t colours, but you only have s < t colours available. Then it is an easy observation that you can still properly colour at least a fraction s/t of the vertices of G. (More formally: there exists an induced subgraph H of G such that H is s-colourable and |V(H)| ≥ s/t|V(G)|.) But the situation is less clear when we look at other types of colourings, such as list-colourings, fractional colourings, multi-colourings, etc. In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question forces us to have to look at some surprising parts of combinatorics.

This is joint work with Xinyi Xu.
Jeudi 5 septembre 2024 (14h30) : Sébastien Zeitoun (LIRIS, Université Lyon 1) : Local certification of forbidden subgraphs

Local certification is a distributed mechanism in which nodes of a network have to verify a property of the network. This is done thanks to small pieces of information, called certificates, which are attributed to the vertices by an external entity, often called the prover. It is known that any property can be certified with certificates of size O(n^2) (where n is the number of nodes in the network), simply by writing the map of the whole graph in the certificate of each node. However, for some properties, we can do much better (many properties admit certificates of size polylog(n)). In local certification, for every graph property, the aim is to find the optimal size of the certificates. Here, we will focus on lower and upper bounds for the property that the graph does not contain some other fixed graph H as an induced subgraph (this is also called H-freeness).