Picking Random Vertices (Invited Talk)
Daniel Lokshtanov · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
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.