FPT-Approximation via Random Walks

Instructor : Tanmay Inamdar Affiliation : IIT Jodhpur Abstract : We present a simple viewpoint for designing time-ratio trade-offs for classical fixed-parameter tractable (FPT) optimization problems. At the heart of this approach is a randomized version of a natural "exact branching" algorithm, where each branch is explored with a carefully tuned probability. The approximation guarantee and its corresponding success probability of the resulting randomized branching algorithm can be analyzed by modeling the behavior as a random walk on a suitably defined state space. We illustrate the approach using Vertex Cover, using both the standard parameterization by solution size, and then by the gap between optimum integral and LP solutions. As a corollary, we also obtain time-ratio trade-offs for other problems of interest, including Odd Cycle Transversal, and Almost 2-SAT. This talk is based on a paper with Ishan Chakraborty, Ariel Kulik, Madhumita Kundu, and Saket Saurabh that is to appear in STOC 2026.