Parameter­ized Graph Modification: A Modern Perspective

In a graph modification problem, we are given a graph G as input, and the goal is to apply certain operations on G (such as vertex deletions, edge deletions, additions or contractions) in order to obtain a graph H with some particular property. Typically, we are looking to achieve the desired properties with minimum possible number of "modifications". Many fundamental optimization problems on graphs can be formulated as graph modification problems. For instance, the classical Vertex Cover problem involves vertex deletions and demands an edgeless graph. The Cluster Editing problem is to change G into a disjoint union of cliques with a minimum number of edge deletions or additions. Several specific manifestations of the graph modification problem framework have been extensively studied, both from algorithmic and structural perspectives.

In particular, graph modification problems have received a significant amount of attention in the context of parameterized complexity. In the context of graph modification, the parameter k can be the size of the solution sought for, or it could be a structural parameter, such as treewidth. Over the last few years, our understanding of the parameterized complexity of graph modification problems has greatly improved. Fixed parameter tractable algorithms have been found for a number of fundamental graph modification problems. For several problems, surprising new algorithms with a sub exponential dependence on the parameter have been developed. Other lines of research develop meta-theorems for large classes of problems. In this talk, we will survey some of these developments, with some emphasis on techniques that work in generic scenarios and are particularly useful for the development of meta-theorems.