Séminaire en ligne
Le but de ce séminaire est de permettre à la communauté du GT d'avoir accès à des exposés en ligne réguliers (par exemple pour les personnes plus isolées) mais aussi de se retrouver régulièrement afin d'échanger sur l'actualité du GT.
Prochain séminaire :
Mardi 17 Juin 14h (durée 45 min + questions)
Meike Neuwohner (Math Dept. of London School of Economics and Political Science)
A characterization of unimodular hypergraphs with disjoint hyperedges.
Lien vers le séminaire
Abstract: 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 hypergraphs, 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 matrices 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.
This is a joint work with Marco Caoduro, and Joseph Paat.
Séminaires passés :
Jeudi 17 Avril 14h (durée 45 min + questions)
Nicolas Nisse (I3S, Sophia-Antipolis)
Tree and Path decompositions with small diameter bags in subclasses of planar graphs.
https://scalelite-info.univ-lyon1.fr/playback/presentation/2.3/deb1788b716ce04af06dc1761a32ab0e724bb232-1744890626756, Vidéo
Abstract: Tree/Path decompositions are usually viewed as a way to decompose a graph along small separators. Another possible measure is the diameter of the separators rather than their size. Precisely, the length of a tree-decomposition of a graph G is the maximum diameter of its bags, where the diameter of a bag B equals the maximum of the distance (in G) between any two vertices in B. The treelength (resp., pathlength) of G is the minimum length of its tree/path decompositions. Several metric problems (metric dimension, TSP, compact routing…) can be solved efficiently in bounded tree/path length graphs. Deciding whether a graph has tree/path length at most 2 is NP-complete and there is no 3/2-approximation for treelength unless P=NP. We investigate the complexity of computing these parameters in subclasses of planar graphs such that outerplanar graphs or series-parallel graphs. This talk summarizes joint works with Thomas Dissaux, Guillaume Ducoffe and Simon Nivelle.
Jeudi 20 mars 15h00 (durée 45 min + questions)
Sophie Huiberts (LIMOS, Clermont-Ferrand)
Open problems about the simplex method.
Vidéo
Abstract: The simplex method is a very efficient algorithm. In this talk we see a few of the state-of-the-art theories for explaining this observation. We will discuss what it takes for a mathematical model to explain an algorithm’s qualities, and whether existing theories meet this bar. Following this, we will question what the simplex method is and if the theoretician's simplex method is the same algorithm as the practitioner's simplex method. Along the way I will sprinkle in some historical anecdotes about linear programming and its applications in violating the fundamental human right to adequate food.
Mardi 5 novembre 14h30 (durée 45 min + questions)
Louis Esperet (G-SCOP, Grenoble)
Algebraic and probabilistic methods in graph theory.
Vidéo
Abstract: This talk will be the occasion to discuss the ideas behind several recent results in extremal combinatorics, including the spectacular improvement on Ramsey numbers R(4,t), recently obtained by Mattheus and Verstraete https://arxiv.org/pdf/2306.04007
These results are based on a clever mix of algebraic techniques and uses of the probabilistic method.
Vendredi 27 septembre 14h00 (durée 45 min + questions)
Paul Bastide (LaBRI, Bordeaux)
Distance reconstruction: How to reconstruct a graph while being short-sighted?.
Vidéo
Abstract: Given a connected graph G = (V, E) where V is known and E is hidden, we are provided access to an oracle that can answer the following queries: given u, v in V, the oracle returns the distance of the shortest path between u and v in G. This setup naturally arises in network recovery and phylogenetic reconstruction problems. This talk explores what is known about the query complexity for various classes of graphs and recent developments toward the main open conjecture in the area: is it possible to reconstruct graphs of bounded degree using n*polylog(n) queries, where n denotes the size of V?
Lundi 27 mai 14h00 (durée 45 min + questions)
Chien-Chung Huang (ENS, Paris)
An FPTAS for Connectivity Interdiction.
Vidéo
Abstract: In the connectivity interdiction problem, we are asked to find a global graph cut and remove a subset of edges under a budget constraint, so that the total weight of the remaining edges in this cut is minimized. This problem easily includes the knapsack problem as a special case, hence it is NP-hard.
For this problem, Zenklusen designed a polynomial-time approximation scheme (PTAS), and for the special case of unit edge costs, exact algorithms. He posed the question of whether a fully polynomial-time approximation scheme (FPTAS) is possible for the general case. We give an affirmative answer. For the special case of unit edge costs, we also give faster exact and approximation algorithms.
Mardi 30 avril matin 10h30 (durée 45 min + questions)
Arnaud Mary (LBBE, Lyon)
Subgraph enumeration problems.
Vidéo
Abstract: Given a non planar graph G, how can one efficiently list all planar subgraphs of G ? This task falls into the category of enumeration problems, which have seen many developments in recent years. After an introduction to enumeration problems, we will focus on problems consisting of enumerating the maximal subgraphs of a graph G that satisfy a given hereditary property P. We will cover some classical techniques as well as the most recent results, along with the most significant open questions.
Vendredi 22 mars 10h30 (durée 45 min + questions, suivi d'une discussion sur le format des séminaires suivants)
Alexandre Vigny (LIMOS, Clermont-Ferrand)
Connectivity under vertex failure, logic and algorithm.
Vidéo
Abstract: Connectivity under vertex failure is the problem of testing whether two vertices are still connected after the deletion of several given vertices. We will explain how to solve this problem very efficiently. Our method can solve many more problems, all being expressible in various logics. The well known first-order logic (FO) can express many algorithmic problems on graphs, but fails to express whether two vertices are connected. We will then discuss logics that can express such properties: separator logic and disjoint-path logic.
This talk will contain a mix of algorithmic, logic, and graph theory. I will cover joint work with Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Szymon Toruńczyk.