- Ignasi Sau, Université de Montpellier, France
Graph modification problems with forbidden minors
In a generic graph modification problem, given an input graph G, the goal is to apply some modifications to it, belonging to a prescribed set M (say, vertex deletion or edge contraction), in order to obtain a graph that belongs to a target graph class C (say, a planar graph or a 3-regular graph). Different instantiations of M and C yield a number of well-studied problems such as Vertex Cover or Feedback Vertex Set. A very active line of research studies the parameterized complexity of this family of problems for various choices of the parameter. Of particular relevance is the case where the target graph class C excludes some graph as a minor. The objective of this talk is to survey recent work in this direction, along with some of the most common techniques used in the literature, including the strong interplay of this family of problems with logic.
- Mark de Berg, Eindhoven University of Technology, The Netherlands
Stable Approximation Schemes
In a dynamic optimization problem, the goal is to maintain a solution to an optimization problem under insertions and deletions. We are interested in trade-offs between the stability of the solution and its approximation ratio. To formalize this, we introduce the concept of
k-stable algorithms, which are algorithms that apply at most kchanges to the solution upon each insertion and deletion. We are particularly interested in stable approximation schemes, which are update algorithms that, for any given parameter ε >0, are k(ε)-stable and maintain a solution with approximation ratio~1+ε, where the stability parameter k(ε) only depends on ε and not on the size of the current input. In this talk I will discuss stable approximation schemes for two problems: the Range-Assignment Problem and the Maximum Independent Set Problem. The talk is based on joint work with Arpan Sadhukhan and Frits Spieksma.