Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations

Abstract

In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random $1.5$-approximation algorithm for Vertex Cover, whose running time of $\tilde{O}(1.01657^k)$ substantially improves the best known runnning time of $\tilde{O}(1.0883^k)$ [Brankovic and Fernau, 2013]. For $3$-Hitting Set we present a parameterized random $2$-approximation algorithm with running time of $\tilde{O}(1.0659^k)$, improving the best known $\tilde{O}(1.29^k)$ algorithm of [Brankovic and Fernau, 2012]. The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations of the form: $$p(b,k) = \min_{1\leq j \leq N} \sum_{i=1}^{r_j} \barγ_i^j \cdot p(b-\bar{b}^j_i, k-\bar{k}_i^j),$$ where ${\bar{b}}^j$ and ${\bar{k}}^j$ are vectors of natural numbers, and $\barγ^j$ is a probability distribution over $r_j$ elements, for $1\le j\le N$. Our main theorem asserts that for any $\hat{I}\pm >0$, $$\underset{k\to \infty }{\lim }\frac{1}{k}\cdot \ln p(\lfloor \hat{I}\pm k\rfloor ,k)=-\underset{1\le j\le N}{\max }{M}_j,$$ where $M_j$ depends only on $\hat{I}\pm$, $\barγ^j$, ${\bar{b}}^j$ and ${\bar{k}}^j$, and can be efficiently calculated by solving a simple numerical optimization problem. To prove the theorem we show an equivalence between the recurrence and a stochastic process. We analyze this process using the {\em method of types}, by introducing an adaptation of Sanov's theorem to our setting. We believe our novel analysis of recurrence relations which is of independent interest is a main contribution of this paper.