Calendrier des animations scientifiques

A $q$-colorful graph $(G, f)$ is a graph $G$ together with a vertex-coloring function $f: V(G) \to \{1, \ldots, q\}$. Such graphs naturally capture a wide range of algorithmic problems on graphs involving distinguished sets of terminals. The concept of graph minors extends in a natural way to colorful graphs. However, to understand the complexity landscape of related problems, especially in the presence of terminals, a structural theory of colorful minors is essential. In this talk, we present three structural theorems concerning the exclusion of specific colorful graphs as minors. These are:

1. the rainbow clique — a clique in which each vertex is assigned all colors,

2. the rainbow grid — a grid in which every vertex carries all colors, and

3. segregated grids — all grids with all colors appearing segregated and in sequence on the outer face.

Our results yield a complete answer to the question of when the Erdős–Pósa property holds for colorful minors, for any possible number of colors. Beyond this, they lead to new meta-algorithmic results for graph problems with terminal constraints—problems that fall outside the reach of existing algorithmic frameworks.

Joint work with Evangelos Protopapas and Sebastian Wiederrecht

Two-stage robust optimization with integer recourse is a notoriously difficult class of problems, yet modelling many important applications. In this we talk, we discuss how to heuristically solve these problems, solving the adversarial problem and the outer minimization problem through local search algorithms. We focus on the case where all decision variables as well as the uncertainty are discrete sets. We compare numerically our algorithms with the recent exact algorithm recently proposed in the literature.

TBA