Abstract: We survey some recent graph algorithms that are based on picking a vertex at random and declaring it to be a part of the solution. This simple idea has been deployed to obtain state-of-the-art parameterized, exact exponential time, and approximation algorithms for a number of problems, such as Feedback Vertex Set and 3-Hitting Set. We will also discuss a recent 2-approximation algorithm for Feedback Vertex Set in Tournaments that
is based on picking a vertex at random and declaring it to not be part of the solution.

time: 2026年7月17日(周五)14:30-15:30

venue: 四号科研楼A区518

Speaker bio: Saket Saurabh received his PhD in Computer Science (2008), from The Institute of Mathematical Sciences (IMSc), Chennai. Saurabh spent two years (2007-2009) as a Postdoctoral Fellow at University of Bergen, Norway, and is now a professor at IMSc and at Department of Informatics at the University of Bergen. His main research interests are in graph algorithms, parameterized algorithms and complexity. He has written more than 300 articles, graduated more than 15 PhD students, and mentored around 10 post doctoral fellows. He is a co-author of two books: Parameterized Algorithms and Kernelization theory of parameterized preprocessing.

He is a SwarnaJayanti Fellow in Mathematical Sciences (2018), Fellow of Indian Academy of Sciences (2020), Academia Europaea (2020), and European Association for Theoretical Computer Science (EATCS, 2021). He received the inaugural ACM India Early Career Researcher Award in 2020, and Shanti Swarup Bhatnagar Prize (SSB) for Science and Technology 2021 (Mathematical Science). He is also the recipient of an ERC starting grant and an ERC Consolidator Grants in parameterized algorithms. He was also named one of the ACM Distinguished Members in 2022.