Euiwoong Lee is an assistant professor at the University of Michigan. He got his Ph.D. from Carnegie Mellon University in 2017 and worked as a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley and a postdoc at New York University. His research interests lie in several topics of theoretical computer science including approximation algorithms and hardness of approximation. His work has been recognized by several awards, including NSF CAREER Award, Edmund M. Clarke Dissertation Award, and ICALP Best Student Paper Award.

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

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.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

988 5655 4581

passcode not visible

logged in users only

If you wish to attend the talk but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.