MFCS 2019: Daniel Lokshtanov: Picking Random Vertices

Monday, August 26, 2019

Speaker: Daniel Lokshtanov (University of California at Santa Barbara (UCSB))

 

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.