Fedor Fomin

Bergen University, Norway and St Petersburg department of Steklov Mathematical Institute

 Graph Modification Problems: A modern perspective

Abstract. In  network (or graph) modifications problem  we have to modify  (repair, improve, or adjust) a network  to  satisfy specific required properties while keeping the cost of the modification to the minimum. The commonly adapted mathematical model in the  study of network problems  is the  graph modification problem. This is a fundamental  unifying problem with a tremendous number of applications in various disciplines like machine learning, networking, sociology, data mining, computational biology, computer vision, and numerical analysis,  and many others.
In this talk we give an overview of recent results and techniques in parameterized algorithms for graph modification problems.