Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems

The field of parameterized approximations aims to derive approximation algorithms which run in parameterized running time. In the classic setting, the considered problem is one which is not expected to have an exact parameterized algorithm, and further has a hardness of approximation lower bound which indicates that a polynomial-time $\alpha$-approximation is unlikely to exist, for some $\alpha >1$. In such a setting, the objective is to derive a $\beta$-approximation algorithm that runs in parameterized running time for , or to show that such an algorithm cannot exist (subject to common complexity assumptions). In recent years, there has been a surge of breakthrough results in the field, providing both algorithms (e.g., [27, 21, 15, 32, 31, 4, 1, 14, 23]) and hardness of approximation results (e.g., [22, 29, 36, 11, 5, 33, 25, 30, 12]).

Within the broad field of parameterized approximations, a subset of works consider problems which are in FPT. For problems in FPT, there is always a parameterized $\beta$-approximation algorithm for all $\beta \ge 1$, as the exact algorithm is also an approximation algorithm. Therefore, the main focus of these works is on the trade-off between approximation and running time.

A prominent approach to attain such parameterized-approximation algorithms relies on using existing exact parameterized algorithms as black-box. In [6], the authors showed that an exact parameterized $c^k\cdot n^{𝒪(1)}$ algorithm for Vertex Cover implies a parameterized $\beta$-approximation in time $c^{(2-\beta )k}$. The same running time has been attained for Vertex Cover by Fellows et al. [19] through a more generic framework which can be applied to additional problems.

Other works focused on directly designing parameterized approximation algorithms. In [8, 7] Brankovic and Fernau provided parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set. The designed algorithms are branching algorithms that involve branching rules aimed at approximation and interleave approximative reduction rules. The works provide, among others, a parameterized $1.5$-approximation for Vertex Cover in time ${1.0883}^k\cdot n^{𝒪(1)}$ and a parameterized $2$-approximation for $3$-Hitting Set in time ${1.29}^k\cdot n^{𝒪(1)}$.

In [26], Kulik and Shachnai showed that the use of randomized branching can lead to significantly faster parameterized approximation algorithms. In particular, they attained a parameterized $1.5$-approximation for Vertex Cover in time ${1.017}^k\cdot n^{𝒪(1)}$ and a parameterized $2$-approximation for $3$-Hitting Set in time ${1.0659}^k\cdot n^{𝒪(1)}$. The idea in randomized branching is that the algorithm picks one of the branching options at random. Subsequently, a good approximation is attained as long as the randomly picked options are not too far from the correct options. The branching rules used by [26] are fairly involved in comparison to the sampling steps used by this paper and their analysis requires non-trivial mathematical machinery.

While [26] showed that randomized branching is a powerful technique for the design of parameterized approximation algorithms, it has only been applied to a limited set of problems. In [26], the authors provided applications of the technique to Vertex Cover and $3$-Hitting Set. Furthermore, for approximation ratios close to $1$, the randomized-branching algorithms are inferior to the exact algorithms in terms of running times (or to the combination of those with [19]). A central goal of this paper is to overcome some of these difficulties: Sampling with a Black Box leverages the power of randomized branching, it is applicable to a wide set of problems, and always improves upon the running times attained using the best known exact algorithms in conjunction with [19].

In [24], the authors developed parameterized approximation algorithms for FVS using the combination of a randomized branching rule for FVS and existing algorithms as black box. Their work indeed served as a motivation for this paper. While [24] uses randomized branching, the work does not facilitate the full power of randomized branching for approximation. In [24], for the algorithm to succeed, the randomized branching must always select the “correct” branching option, while a main benefit of randomized branching for approximation is that an incorrect option may still lead to an approximate solution ³³3[24] presents three different algorithms. One of the algorithms does utilize this property of randomized branching. However, the specific algorithm is a plain randomized branching algorithm which does not use an exact parameterized algorithm or a polynomial-time approximation algorithm as a black box. . The faster running times attained in this paper are a result of a better utilization of randomized branching for parameterized approximations. While the approach in [24] can potentially be generalized to other problems, such as $3\text{-Path Vertex Cover}$, the resulting running time would be inferior to the ones attained by Sampling with a Black Box.

The concept of randomly sampling a partial solution and subsequently extending it using a parameterized algorithm is central to the monotone local search technique of Fomin, Gaspers, Lokshtanov and Saurabh [20]. Later variants of the technique are designed to obtain exponential time approximation algorithms [16, 17, 18]. A central idea in those later variants is that an approximate solution is obtained as long as the initial sampling does not contain too many vertices which do not belong to the optimum. This resembles the use of the sampling step in this paper.

The focus of this paper is the class of $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ problems. For any hypergraph property $\mathrm{\Pi }$ and a closed set of hypergraphs $𝒢$, the input for $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ ($(𝒢,\mathrm{\Pi })\text{-Del}$ for short) is a hypergraph $G\in 𝒢$. A solution is a subset of vertices $S\subseteq V(G)$ such that $G\setminus S\in \mathrm{\Pi }$. We use ${\text{SOL}}_{\mathrm{\Pi }}(G)=\{S\subseteq V(G)|G\setminus S\in \mathrm{\Pi }\}$ to denote the set of all solutions. The objective is to find a smallest cardinality solution $S\in {\text{SOL}}_{\mathrm{\Pi }}(G)$. In the decision version of the problem, we are given a hypergraph $G\in 𝒢$, an integer $k\ge 0$ and we are asked whether there exists a set $S\in {\text{SOL}}_{\mathrm{\Pi }}(G)$ such that $\left|S\right|\le k$.

The family of $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ problems include many well known problems. Some notable examples are:

• $\mathrm{■}$

  Vertex Cover. In this case $𝒢$ corresponds to graphs, i.e., hypergraphs with edge cardinality exactly 2. The hypergraph property $\mathrm{\Pi }$ consists of all edgeless graphs.

• $\mathrm{■}$

  Vertex Cover on graphs with maximal degree $3$. In this case $𝒢$ corresponds to graphs of maximal degree $3$ or less. The property $\mathrm{\Pi }$, again, consists of all edgeless graphs.

• $\mathrm{■}$

  $d$-Hitting Set. Similar to Vertex Cover, in this case $𝒢$ corresponds to hypergraphs with edge cardinality at most $d$. $\mathrm{\Pi }$ also consists of all edgeless hypergraphs.

• $\mathrm{■}$

  Feedback Vertex Set. In this case $𝒢$ is the set of all graphs and $\mathrm{\Pi }$ is the set of graphs that have no cycles.

We use ${\text{OPT}}_{𝒢,\mathrm{\Pi }}(G)$ to denote the size of an optimal solution for $G\in 𝒢$ with respect to the $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ problem. That is, ${\text{OPT}}_{𝒢,\mathrm{\Pi }}(G)=\min \left\{\left|S\right||S\in {\text{SOL}}_{\mathrm{\Pi }}(G)\right\}$. If $𝒢$ and $\mathrm{\Pi }$ are known by context we use OPT instead of ${\text{OPT}}_{𝒢,\mathrm{\Pi }}$.

Our goal is to develop parameterized approximation algorithms for $(𝒢,\mathrm{\Pi })$-Vertex Deletion problems, where the parameter is the solution size. Such algorithms return a solution of size $\alpha \cdot k$ or less (with probability at least $\frac{1}{2}$) if the optimum of the instance is at most $k$.

We note that the above definition of parameterized approximation algorithms captures the classic definition of exact parameterized algorithms ($\alpha =1$) and polynomial-time approximation algorithms ($f(k)=O(1)$) as special cases. Sampling with a Black Box converts a randomized parameterized $\alpha$-approximation algorithm $𝒜$ which runs in time $c^k\cdot n^{𝒪(1)}$ to a randomized parameterized $\beta$-approximation algorithm $ℬ$ that runs in time $d^k\cdot n^{𝒪(1)}$. The conversion relies on a simple problem dependent sampling step. In all our applications the algorithm $𝒜$ is either the state-of-art exact parameterized algorithm (i.e., $\alpha =1$), or the state-of-art polynomial-time algorithm (i.e., $c=1$) for the problem.

We exploit inherent properties of a specific $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ problem to come up with basic sampling strategies. From a high-level perspective, a sampling step is a polynomial-time algorithm that takes as input a hypergraph $G\in 𝒢\setminus \mathrm{\Pi }$ and returns a vertex $v\in V(G)$, such that the size of the optimal solution of $G\setminus v$ decreases by $1$, with a prescribed probability.

For example, consider Vertex Cover, which is the $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ problem where $𝒢$ is the set of all graphs and $\mathrm{\Pi }$ consists of all edgeless graphs. The following is a very simple sampling step for Vertex Cover with success probability $\frac{1}{2}$: pick an arbitrary edge and return each of its endpoints with probability $\frac{1}{2}$. This algorithm clearly runs in polynomial-time. Moreover, for each Vertex Cover $S$ of $G$ and for each edge $e$, at least one of the endpoints of $e$ belongs to $S$. Therefore, it is a sampling step with success probability $q=\frac{1}{2}$ for Vertex Cover. We provide sampling steps for the general case where $\mathrm{\Pi }$ is defined by a finite set of forbidden subgraphs, for Feedback Vertex Set and for Pathwidth One Vertex Deletion.

On their own, sampling steps can be easily used to derive parameterized approximation algorithms. To obtain a $\beta$-approximation, one may use the sampling step $\beta \cdot k$ times, where each execution returns a vertex $v$ which is removed from the graph and added to the solution $S$. After $\beta \cdot k$ steps, with some probability $P$, the set $S$ of returned vertices is indeed a solution. Thus, by repeating this multiple sampling step for $\frac{1}{P}$ times, one gets a $\beta$-approximate solution with probability $\frac{1}{2}$. By carefully tracing the probability in the above argument, we show that $P\approx {\left(\exp (\beta \cdot 𝒟(\frac{1}{\beta }\parallel q))\right)}^{-k}$, as demonstrated by the following lemma.⁴⁴4Recall $𝒟(\cdot \parallel \cdot )$ stands for the Kullback-Leibler divergence which has been defined in Section 2.

The proof of Lemma 3 can be found in Section 5. Observe that $\exp (\frac{1}{q}\cdot 𝒟(\frac{1}{\left(\frac{1}{q}\right)}\parallel q))=1$ for every $q\in (0,1)$. Thus, Lemma 3 provides a randomized polynomial-time $\frac{1}{q}$-approximation algorithm for $(𝒢,\mathrm{\Pi })\text{-Del}$. This justifies the restriction of the lemma to $\beta \le \frac{1}{q}$.

While Lemma 3 provides a parameterized $\beta$-approximation algorithm for essentially any $\beta$, the resulting algorithms are often far from optimal. For example, for Feedback Vertex Set (FVS) we provide a sampling step with success probability $\frac{1}{4}$. Thus, by Lemma 3 we get a randomized parameterized $1.1$-approximation for FVS which runs in time $\approx {2.944}^k\cdot n^{𝒪(1)}$. However, FVS has an exact randomized parameterized algorithm which runs in time ${2.7}^k\cdot n^{𝒪(1)}$. That is, the running time of the approximation algorithm is slower than that of the exact algorithm. Our goal is to combine the sampling step with the exact algorithm to attain improved running time in such cases.

Our main theorem states the following: a sampling step with success probability $q$, together with a parameterized $\alpha$-approximation algorithm $𝒜$ which runs in time $c^k\cdot n^{𝒪(1)}$, can be used to obtain a $\beta$-approximation algorithm $ℬ$. By Lemma 3, the sampling step can be used to obtain a randomized parameterized $\alpha$-approximation which runs in time ${\left(\exp (\alpha \cdot 𝒟(\frac{1}{\alpha }\parallel q))\right)}^k\cdot n^{𝒪(1)}$. Our assumption is that $𝒜$ is at least as fast as the algorithm provided by Lemma 3, hence we only consider the case in which $c\le \exp (\alpha \cdot 𝒟(\frac{1}{\alpha }\parallel q))$.

We use the following functions to express the running time of $ℬ$. Define ${\delta }_{\text{left}}^{\ast }(\alpha ,c,q)\in (1,\alpha ]$ and ${\delta }_{\text{right}}^{\ast }(\alpha ,c,q)\in [\alpha ,\frac{1}{q}]$ to be the unique numbers which satisfy

We write ${\delta }_{\text{left}}^{\ast }={\delta }_{\text{left}}^{\ast }(\alpha ,c,q)$ and ${\delta }_{\text{right}}^{\ast }={\delta }_{\text{right}}^{\ast }(\alpha ,c,q)$ if the values of $\alpha ,c$ and $q$ are clear from the context. The following lemma provides conditions which guarantee that ${\delta }_{\text{left}}^{\ast }$ and ${\delta }_{\text{right}}^{\ast }$ are well defined in certain domains.

The proof of Lemma 4 is included in the full version of the paper. We note that $𝒟(\frac{1}{\alpha }\parallel \frac{1}{x})$ is monotone in the domains $x\in (1,\alpha ]$ and $x\in [\alpha ,\mathrm{\infty })$. Hence the values of ${\delta }_{\text{left}}^{\ast }(\alpha ,c,q)$ and ${\delta }_{\text{right}}^{\ast }(\alpha ,c,q)$ can be easily evaluated to arbitrary precision using a simple binary search.

We use ${\delta }_{\text{left}}^{\ast }$ and ${\delta }_{\text{right}}^{\ast }$ to express the running time of $ℬ$. For every $\beta ,\alpha \ge 1$, and $c\ge 1$ such that $c\le \exp (\alpha \cdot 𝒟(\frac{1}{\alpha }\parallel q))$, we define

As we can compute ${\delta }_{\text{left}}^{\ast }$ and ${\delta }_{\text{right}}^{\ast }$, it follows we can also compute $\text{convert}(\alpha ,\beta ,c,q)$ to arbitrary precision.

Recall that Lemma 3 provides a polynomial-time $\frac{1}{q}$-approximation algorithm for $(𝒢,\mathrm{\Pi })$- Del. Consequently, we restrict our consideration to $\alpha$ and $\beta$ values that are less than or equal to $\frac{1}{q}$. Our main technical result is the following.

The proof of Theorem 5 is given in Section 5. For example, by Theorem 5, we can use the sampling step with success probability $\frac{1}{4}$ for FVS, together with the randomized exact parameterized algorithm for the problem which runs in time ${2.7}^k\cdot n^{𝒪(1)}$ [28], to get a randomized parameterized $1.1$-approximation algorithm with running time ${2.49}^k\cdot n^{𝒪(1)}$. The algorithm achieves a better running time than that of the exact parameterized algorithm, as well as the running time which can be attain solely by the sampling step, i.e. ${2.944}^k\cdot n^{𝒪(1)}$ (Lemma 3). We note that this running time is also superior to the running time of ${2.62}^k\cdot n^{𝒪(1)}$ for the same approximation ratio given in [24].

The running time of the algorithm generated by Theorem 5 (i.e., the value of $\text{convert}(\alpha ,\beta ,c,q)$) can always be computed efficiently, though this computation requires a binary search for the evaluation of ${\delta }_{\text{right}}^{\ast }$ and ${\delta }_{\text{left}}^{\ast }$. For the special cases of $\alpha =1$ and well as ($\alpha =2$ and $c=1$) we provide a closed form expression for $\text{convert}(\alpha ,\beta ,c,q)$.

Both Theorems 6 and 7 follow from a closed form formula which we can attain for ${\delta }_{\text{right}}^{\ast }$ or ${\delta }_{\text{left}}^{\ast }$ for the specific values of $\alpha$ and $c$ considered in the theorems. The proofs of Theorems 6 and 7 are given in the full version of the paper.

We compare Sampling with a Black-Box with the technique of [19] for $(𝒢,\mathrm{\Pi })$-Vertex Deletion  problems in which $\mathrm{\Pi }$ is defined by a finite set of forbidden vertex induced hypergraphs.

We note that ${\mathrm{\Pi }}^{\mathrm{\Omega }}$ is always hereditary and polynomial-time decidable. We also note the the family of graphs properties defined by a finite set of forbidden hypergraph suffices to define many fundamental graph problems such as Vertex Cover, $d$-Hitting Set and $\mathrm{\ell }$-Path Vertex Cover.

For a set of hypergraphs $\mathrm{\Omega }=\{F_1,\mathrm{\dots },F_{\mathrm{\ell }}\}$, define $\eta (\mathrm{\Omega })≔{\max }_{1\le i\le \mathrm{\ell }}\left|V\left(F_i\right)\right|$, the maximal number of vertices of a hypergraph in $\mathrm{\Omega }$. The following result has been (implicitly) given in [19].

There is a simple and generic way to design a sampling step for ${\mathrm{\Pi }}^{\mathrm{\Omega }}$. The sampling step finds a set of vertices $S\subseteq V(G)$ of the input graph such that $G[S]$ is isomorphic for a graph in $\mathrm{\Omega }$, and returns a vertex from $S$ uniformly at random. This leads to the following lemma.

A formal proof for Lemma 10 is given in the full version of the paper. Together with Theorem 5 the lemma implies the following.

Observe that Lemma 9 and Corollary 11 only differ in the resulting running time. The following lemma implies that for every the running time of Sampling with a Black Box, as given in Corollary 11, is always strictly better than the running time of [19] as given in Lemma 9.

The proof of Lemma 12 is given in the full version of the paper.

Recall that given a graph $G$ and integer $k$, the Feedback Vertex Set (FVS) problem asks whether there exists a set $S\subseteq V(G)$ of size at most $k$ such that $G\setminus S$ is acyclic. FVS can also be described as a $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ problem, where $𝒢$ is the set of all graphs and $\mathrm{\Pi }$ is the set of graphs that have no cycles. First, we demonstrate that there exists a sampling step for FVS.

The proof of Lemma 13, included in the full version of the paper, analyzes a sampling step that begins by removing vertices of degree at most 1. Then, a vertex is sampled from the remaining vertices, where the sampling probability for each vertex is proportional to its degree in the remaining graph. The proof of Lemma 13 relies on ideas from [3], which were also similarly used by [24]. Unlike [3, 24], Lemma 13 avoids the use reduction rules which modify the graph. This technical difference is essential for meeting the formal definition of a sampling step.

In [28], the authors present a randomized parameterized algorithm which runs in time ${2.7}^k\cdot n^{𝒪(1)}$ for FVS (i.e., in the terminology of this paper, $\alpha =1,c=2.7$). Moreover, FVS also has a 2-approximation algorithm that runs in polynomial-time (i.e., $\alpha =2$, $c=1$) [2]. Using the sampling step together with Theorem 5 we attain the following.

The proof of Theorem 14 is provided in the full version of the paper. It leverages the FPT algorithm presented in [28] and the 2-approximation algorithm introduced in [2], alongside Theorems 6 and 7.

In [24], the authors present a $\beta$-approximation algorithm for each . It can be visually (see Figure 1(a)) and numerically (see Table 1) verified that our algorithms demonstrates a strictly better running-time.

Given a graph $G$ and integer $k$, the Pathwidth One Vertex Deletion (POVD) problem asks whether there exists a set $S\subseteq V(G)$ of size at most $k$ such that $G\setminus S$ has pathwidth at most $1$ (see [13] for the definition of pathwidth). Initially, we demonstrate that there exists a sampling step for POVD.

The proof of Lemma 15 can be found in the full version of the paper. The sampling step for POVD is very similar to that for FVS, with a slight modification. This follows from the known property that a graph has pathwidth at most $1$ if and only if it is acyclic and does not contain a specific graph of $7$ vertices as a vertex induced subgraph. Due to this additional forbidden subgraph, POVD has a sampling step with probability $\frac{1}{7}$, instead of $\frac{1}{4}$ as in the case of FVS.

To the best of our knowledge, parameterized approximation algorithms have not been studied for POVD. However, there exists an FPT algorithm for POVD with running time ${3.888}^k\cdot n^{𝒪(1)}$ ($\alpha =1,c=3.888$) [34]. Next, we demonstrate how combining the aforementioned sampling step with a parameterized algorithm yields a new approximation algorithm. Refer to Figures 2 and 2 for the corresponding running times.

The proof of Theorem 16, included in the full version of the paper, uses the FPT algorithm from [34] together with Theorem 6.

There are many problems that can be described as $(𝒢,\mathrm{\Pi })$-Vertex Deletion  problems in which $\mathrm{\Pi }$ is defined by a finite set $\mathrm{\Omega }$ of forbidden vertex induced hypergraphs. For each of those problems, by Lemma 10 there exists a sampling step with success probability $\frac{1}{\eta }$, where $\eta$ is the maximum number of vertices of a hypergraph in $\mathrm{\Omega }$. In the following, we will demonstrate how we can obtain parameterized approximation algorithms for such problems. For the sake of presentation, we will focus on a specific problem called $3$-Path Vertex Cover. We provide additional examples in the full version of the paper.

Given a graph $G$, a subset of vertices $S\subseteq V(G)$ is called an $\mathrm{\ell }\text{-path Vertex Cover}$ if every path of length $\mathrm{\ell }$ contains a vertex from $S$. The $\mathrm{\ell }\text{-Path Vertex Cover}$ problem asks whether there exists an $\mathrm{\ell }\text{-path Vertex Cover}$ of size at most $k$ where $k$ is the parameter [9]. $\mathrm{\ell }\text{-Path Vertex Cover}$ can be described as a $(𝒢,\mathrm{\Pi })\text{-Vertex Deletion}$ where $𝒢$ is the set of graphs and $\mathrm{\Pi }$ is the set of graphs with maximum path length at most $\mathrm{\ell }-1$. Alternatively, let $\mathrm{\Omega }$ be the set of all graphs $G$ with $\mathrm{\ell }$ vertices such that $G$ contains a path on $\mathrm{\ell }$ vertices. It holds that $\mathrm{\ell }\text{-Path Vertex Cover}$ is equivalent to $(𝒢,{\mathrm{\Pi }}^{\mathrm{\Omega }})\text{-Vertex Deletion}$. Moreover, by definition of $\mathrm{\Omega }$ we have that $\eta (\mathrm{\Omega })≔\mathrm{\ell }$. Therefore, by Lemma 10, there is a sampling step for $\mathrm{\ell }\text{-Path Vertex Cover}$ with success probability $\frac{1}{\mathrm{\ell }}$.

In the following, we will consider $\mathrm{\ell }=3$, i.e. the problem $3$-Path Vertex Cover. There exists an FPT algorithm for $3$-Path Vertex Cover which runs in time ${1.708}^k\cdot n^{𝒪(1)}$ ($\alpha =1,c=1.708$) [10]. Moreover, there is also a 2-approximation algorithm that runs in polynomial-time ($\alpha =2,c=1$) [35].

The proof of Theorem 17, detailed in the full version of the paper, combines the FPT algorithm from [10] with the polynomial-time 2-approximation algorithm from [35]. Leveraging Theorems 6 and 7, we derive approximation algorithms and select the one with the smaller running time based on the approximation ratio.

Using the technique of [19] (see Lemma 9) one can attain a $\beta$-approximation algorithm for $3$-Path Vertex Cover with running time ${1.708}^{\frac{3-\beta }{2}\cdot k}\cdot n^{𝒪(1)}$, for every $1\le \beta \le 2$. As can be visually (see Figure 1(b)), numerically (see Table 3) or formally (see Lemma 12) verified, our algorithm has a strictly better running time for all values of .