CS Theory Colloquium Series
Fall 2023
|
Monday, October 16th, 3:30pm, Harold Frank Hall (HFH) room 1132 Speaker: Jie Xue (NYU Shanghai) Title: Vertex Deletion on Disk Graphs Abstract: Abstract: In a vertex-deletion problem, the input is a graph G and the goal is to delete a minimum subset X of vertices from G such that the resulting graph G-X satisfies some desired property. Vertex-deletion problems are among the most fundamental NP-complete optimization problems in algorithmic graph theory and have been well- studied over decades. Unfortunately, most vertex-deletion problems are very hard in the sense that they are unlikely to admit (polynomial-time) approximation schemes or subexponential-time algorithms. However, when the input graph lies in restrictive graph classes, e.g., planar graphs, unit-disk graphs, etc., the vertex-deletion problems can become substantially easier --- by exploiting nice structures of these graphs, people have obtained efficient approximation and exact algorithms for many instances of vertex deletion. In this talk, we shall consider vertex-deletion problems on an important class of geometric intersection graphs, i.e., disk graphs, which characterize the intersection pattern of disks in the plane and generalize both planar graphs and unit-disk graphs. Specifically, we shall discuss recent development of approximation schemes and subexponential-time (parameterized) algorithms for vertex deletion on disk graphs. Bio: Jie Xue is an Assistant Professor at New York University Shanghai. Previously, he was a postdoctoral scholar at UCSB. He obtained his Ph.D. degree in Computer Science with a minor in Mathematics at the University of Minnesota, Twin Cities. His research interests include Computational Geometry, Algorithms & Data Structures, Graph Theory, Parameterized Complexity, etc. Specifically, his research mainly focuses on designing efficient algorithms and data structures for solving geometric problems and graph problems. |