Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks

In the last decade, FPT approximation has witnessed tremendous growth, with the development of several powerful upper- and lower-bound techniques. Within this framework, a newly emerging direction focuses on problems that admit algorithms with running time of the form ck · nO(1) for some constant c. This line of inquiry naturally leads to the notion of time–approximation ratio trade-offs (or time-ratio trade-offs): by relaxing the approximation guarantee in a controlled manner, one can improve the exponential dependence on the parameter in the running time. The contribution of this paper is threefold: (i) a formal language for parameterized randomized branching algorithms (called Oracle Subset Problems); (ii) a meta-algorithm applicable to all problems expressible in this language; and (iii) new time–ratio trade-offs obtained by instantiating the framework on fundamental problems, including Above-Guarantee Vertex Cover (parameterized by excess over the LP lower bound), Odd Cycle Transversal, Node Multiway Cut, Subset/Group Feedback Vertex Set, Min-Weight d-SAT, and Matroid-Rank d-Hitting Set (where solution is measured by the rank in a matroid accessible via an independence oracle), among others. Our applications demonstrate substantially broader applicability. For the first time, they apply to cut problems, problems with parity constraints (Odd Cycle Transversal), “complex” cycle hitting problems (hitting all cycles whose length mod73 is non-zero), and even a generalization where the user specifies the subset of vertices such that only the cycles passing through that subset of vertices should be hit. These results are obtained by developing time–ratio trade-offs for two meta-algorithms, expressed in our language: (i) the biased-graph framework [Wahlström, SODA 2017; Lee and Wahlström, arXiv 2020], and (ii) the Vertex Cover above LP framework [Lokshtanov et al., TALG 2014].