For a family F of graphs, the F-Deletion Problem asks to remove the minimum number of vertices from a given graph G to ensure that G belongs to F. One of the most common ways to obtain an interesting family F is to fix another family H of graphs and let F be the set of graphs that do not contain any graph H as some notion of a subgraph, including (standard) subgraph, induced subgraph, and minor. This framework captures numerous basic graph problems, including Vertex Cover, Feedback Vertex Set, and Treewidth Deletion, and provides an interesting forum where ideas from approximation and parameterized algorithms influence each other. In this talk, I will give a brief survey on the state of the art on the F-Deletion Problems for the above three notions of subgraphs, and talk about a recent result on Weighted Bond Deletion.
|
