A typical graph modification problem aims to modify a graph G, via a small number of operations from a specified set S, into some other graph H that has a certain desired property, which usually describes a certain graph class G to which H must belong. In this way a variety of classical graph-theoretic problems is captured. For instance, if only k vertex deletions are allowed and H must be an independent set or a clique, we obtain the Independent Set or Clique problem, respectively.
Now, instead of fixing a particular graph class G, we fix a certain graph parameter π. That is, given a graph G, a set S of one or more graph operations and an integer k, we ask whether G can be transformed into a graph G' by using at most k operations from S, such that π(G') ≤ π(G)-d for some threshold d ≥ 0. Such problems are called blocker problems, as the set of vertices or edges involved can be seen as ``blocking'' some desirable graph property (such as being colorable with only a few colors). Identifying the part of the graph responsible for a significant decrease of the parameter under consideration gives crucial information on the graph.
Blocker problems have been given much attention over the last few years. In this talk, I will give an overview of recent results on this topic.