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