Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii

Set cover is among the most popular optimization problems, where given a ground set of elements and a family of subsets of the ground set, the goal is to find a minimum-sized subfamily of those subsets whose union contains all elements of the ground set. The problem admits a polynomial-time (poly-time) $O(\log n)$-approximation, and this bound is known to be tight [16, 14]. Set cover has been studied in various restricted settings with the goal of achieving better approximation factors. One such interesting setting is geometric covering, where elements are points in a geometric space, and subsets are induced by geometric objects such as disks and squares. Such restricted covering problems can admit poly-time constant-approximations [11, 9] or even approximation schemes [17, 27, 10], as one can exploit the natural constraints imposed by geometric spaces and objects. Indeed, this turned out to be a very popular area of research, as many practical problems can be described in geometric terms, e.g., in areas such as sensor networks, computational biology, image processing, and VLSI design [29, 6, 15, 13, 17].

While several formulations of geometric set cover are now well-studied, their real applications are sometimes hindered by practical constraints. There exist well-established techniques like local search [27, 19, 7, 1] to compute near-optimal solutions to fundamental geometric problems, but real-life constraints can invalidate the assumptions needed by these approaches. In this work, we study one such problem motivated by applications in wireless and sensor networks, which was introduced by Maheshwari et al. [22]. Informally, given a set of access points and users, the goal is to assign either low-range high frequency (i.e., high speed) or large-range low frequency to each access point, maximizing the number of users in high-frequency range while ensuring that each user is in the range of at least one access point of either kind.

We use the following notation to define the problem. For any point $x$ and a real $\rho >0$, let $D(x,\rho )$ denote the closed disk with center $x$ and radius $\rho$. In Discrete Covering with Two Types of Radii (DC-2), we are given two point sets $P$ (of $n$ “users”) and $A=\{a_1,a_2,\mathrm{\dots },a_m\}$ (of $m$ “access points”) in the plane, and two real numbers ${\rho }_1$ and ${\rho }_2$, such that and $P\subseteq {\bigcup }_{i=1}^{m}D(a_i,{\rho }_2)$. The goal is to select for each $i=1,2,\mathrm{\dots },m$, a value $r_i\in \{{\rho }_1,{\rho }_2\}$ such that $P\subseteq {\bigcup }_{i=1}^{m}D(a_i,r_i)$ and the gain, i.e., the size of the set $\{p\in P:\text{there is an index }1\le i\le m\text{ such that }{r}_i={\rho }_1$ and $p\in$ $D(a_i,r_i)\}$ is maximized. Thus, we want to select for each $1\le i\le m$, either the small disk (of radius ${\rho }_1$) centered at $a_i$ or the large disk (of radius ${\rho }_2$) centered at $a_i$, such that the set $P$ is covered by the chosen disks and the number of points in $P$ each of which is contained in at least one chosen small disk is maximized.

The problem is known to be NP-hard [22] similar to most of the covering problems with disks. Bandyapadhyay et al. [2] designed a poly-time 4-approximation for DC-2. In their approach, they converted the problem to a weighted covering problem with one type of radii (large) by assigning unit weight for each user point contained in a small disk, to a representative large disk. To solve this covering problem, they compute the Delaunay triangulation of the large disk centers. In particular, this triangulation is a planar graph, and hence can be colored by 4 colors. Consequently, a vertex cover of weight at most $\frac{3}{4}$ of the total weight can be computed, and the corresponding large disks are shown to cover all user points. Thus, at least $\frac{1}{4}$ of the total weight of the large disks remains unused while constructing the cover, which leads to the 4-approximation. Obtaining an improved approximation factor remained an interesting open question, as many covering problems involving unit disks admit PTASes [27, 21, 10].

As mentioned in [2], DC-2 can be interpreted as a combination of two problems: Minimum Weight Unit Disk Cover (WUDC) and Maximum Coverage with Unit Disks (MCUD). In WUDC, the goal is to select a subset of unit disks that cover all input points such that the sum of the weights of the selected disks is minimized. In MCUD, for a given $k$, the goal is to select a subset of $k$ unit disks that cover the maximum number of points possible. Both of these problems are well-studied in computational geometry.

Mustafa and Ray [27] developed a PTAS for WUDC when all weights are equal, i.e., for the unweighted version. Their approach, which relies on a local search scheme, is inadequate for addressing weighted instances. Finding the optimal cover even for weighted unit disks has long been known to be strongly NP-hard [18]. Regardless, approaches have been developed in the last two decades for computing approximate solutions for weighted covering problems for broad classes of objects, such as those with low union complexity [8, 11, 30, 4]. Chan et al. [9] designed constant approximations for covering with weighted disks. Subsequently, Li and Jin [21] designed a PTAS for WUDC, utilizing a shifting strategy [18] that partitions the plane into squares and addresses a restricted version of the problem within each square. We note that this approach cannot be used directly for DC-2 when users are covered by multiple small disks, because the assignment of user weights to small disks cannot be done arbitrarily, and so the weight of a small disk in the optimal solution is an unknown in DC-2.

Chaplick et al. [10] designed a local search PTAS for the MCUD problem. It follows that for some $k$, there are $k$ small disks in any optimal solution to DC-2 such that they cover the points that contribute to the optimal gain. However, the best set of $k$ small disks that maximizes the coverage might not lead to a feasible solution, as the remaining $n-k$ large disks might not cover the points not in the union of the chosen small disks. Dealing with two different but dependent tasks is the main challenge in tackling DC-2. The need to satisfy one objective while optimizing another necessarily means that any decision made at the local scope can have global consequences. For example, selecting one access point for a small disk may force a neighbor to be selected as a large disk to maintain coverage, and such a dependency may further propagate to disks that are far away. As such, any solution for this kind of constrained problem must take into account its global properties while making any decision to achieve good approximation.

We also study DC-2 from the perspective of parameterized complexity. Designing parameterized algorithms for geometric problems is an active area of research that is becoming increasingly popular. A problem is called fixed-parameter tractable (FPT) in a parameter $k$ if it can be solved in time $f(k)\cdot n^{O(1)}$ for a computable function $f$, where $n$ is the input size. A known fact is that if a problem with parameter $k$ is W[1]-hard, then it cannot be FPT in $k$ [12]. Marx [23] considered the problem of covering with unit squares. Here the size of a cover is a natural parameter. He proved that the problem is W[1]-hard. One consequence of this is that the optimization version does not admit an Efficient PTAS or EPTAS [23], i.e., the $n^{O(1/{ϵ}^2)}$-time PTAS due to Hochbaum and Maass [17] cannot be improved to an EPTAS. In a different work, Marx [24] studied the parameterized complexity of common optimization problems in geometric intersection graphs and obtained a mixed set of algorithmic and hardness results. In a follow-up work, Marx and Pilipczuk [26] designed a framework for designing sub-exponential ($n^{O(\sqrt{k})}$) time algorithms for a wide range of geometric facility location problems. Applying this framework, they designed an $n^{O(\sqrt{k})}$-time algorithm for covering with unit disks. This result is also tight, assuming ETH [24] (also see this survey [25]). The framework is based on Voronoi diagram separators. We note that this framework is not useful for DC-2, again due to the mixed nature of the problem. Kowalska and Pilipczuk [20] recently studied parameterized approximation algorithms for covering with line segments. Lastly, Banik et al. [3] studied the parameterized complexity of a conflict-free version of geometric covering.

Our main algorithm is an aggregate of two separate algorithms. The first is based on the Delaunay triangulation of large disk centers. The second algorithm is based on a reduction to the Minimum Weight Unit Disk Cover problem. Thereafter, we combine the two algorithms to obtain our main algorithm which has the desired approximation guarantee.

A set of disks $D^{\prime }$ is said to cover a set of points $P^{\prime }$ if the union of the disks in $D^{\prime }$ contains the points in $P^{\prime }$. Let $S$ (resp. $L$) be the set of small (resp. large) disks centered at the access points in $A$. Let $V\subseteq P$ such that each point in $V$ does not lie in any (small) disks of $S$. Wlog, we assume that each point of $V$ is in at least two disks of $L$. It must be in at least one disk, otherwise there is no feasible cover. Also, if it is in exactly one disk, this disk will always be part of the solution. Let $N\subseteq P$ such that each point in $N$ lies in at least one (small) disk of $S$. Thus, $(V,N)$ is a partition of $P$. Let $N_1\subseteq N$ such that each point in $N_1$ lies in exactly one disk of $S$. Similarly, let $N_2\subseteq N$ such that each point in $N_2$ lies in at least two disks of $S$. Thus, $(N_1,N_2)$ is a partition of $N$. Let $n_1=|N_1|$ and $n_2=|N_2|$. Fix an optimal solution of DC-2, i.e., the selected subset of disks of $S\cup L$. Let OPT be the set of points in $N$ covered by the optimal solution. Let OPT${}_1{}^{}=N_1\cap$ OPT and OPT${}_2{}^{}=N_2\cap$ OPT. Also, fix an error parameter $ϵ>0$.

As each point in $N$ is contained in a small disk $D(a_i,{\rho }_1)$ and also in the corresponding large disk $D(a_i,{\rho }_2)$, the following observation holds.

The parameterized version of DC-2 includes a fixed parameter $k$, where in addition to the original goal, we are assured that $r_i={\rho }_2$ for at most $k$ access points $a_i$. We refer to this problem as Par-DC-2. Here, we reuse the notation from the previous section. Let OPT be the gain of any optimal solution. Recall the sets of small disks $S$ and large disks $L$, and the sets of vulnerable points $V$ and non-vulnerable points $N$. An instance of Par-DC-2 is called $s$-sparse for an integer $s\ge 2$ if each point of $V$ is in at most $s$ large disks of $L$. We note that in such an instance, a point of $N$ can lie in more than $s$ large (or small) disks. We prove that Par-DC-2 is fixed-parameter tractable in $k+s$.

For a set $S^{\prime }\subseteq S$, let the gain of $S^{\prime }$ be the number of points of $N$ contained in the disks of $S^{\prime }$. For a subset of large disks $L^{\prime }\subseteq L$, let sm$(L^{\prime })$ be the set of corresponding small disks.

Next, we describe our algorithm. Our algorithm is based on a recursive branching strategy. Algorithm 2 shows the pseudo-code of a recursive subroutine that is the main procedure used by our algorithm. The subroutine Recursive-Branching$(V^{\prime },L^{\prime },l)$ takes as input a subset of points $V^{\prime }\subseteq V$ that are yet to be covered, a subset $L^{\prime }\subseteq L$ of disks already chosen to cover, and an integer $l>0$ that denotes the depth of recursion. The subroutine returns a True/False flag. If the flag is True, it also outputs a set of $k$ large disks $L_1^{\prime }\supset L^{\prime }$ such that $L_1^{\prime }\setminus L^{\prime }$ covers $V^{\prime }$, and the gain $g$ corresponding to the solution $L_1^{\prime }$, i.e., the gain of sm$(L\setminus L_1^{\prime })$. Inside the subroutine, we first check if $V^{\prime }$ is empty, and if that is the case, $L^{\prime }$ itself is returned as the solution along with its gain. If the depth $l=k+1$, but $V^{\prime }\ne \mathrm{\varnothing }$, the False flag is returned, indicating there is no feasible solution along this branch, so it should be pruned here. Otherwise, $l\le k$ and $V^{\prime }\ne \mathrm{\varnothing }$. In that case, we consider any arbitrary point $p\in V^{\prime }$. There are at most $s$ large disks in $L$ that cover $p$. We branch on each such large disk $D$. In each branch, we remove the points of $V^{\prime }$ that are covered by $D$ and recurse on the set of remaining points with $L^{\prime }\cup \{D\}$ being the new set of selected disks and $l+1$ as the new depth. We also keep track of the largest gain solution returned by these calls and return it if the flag counter $b$ is set to True. If $b$ is False, we return the False flag.

The main algorithm makes a call to Recursive-Branching$(V,\mathrm{\varnothing },1)$. If the call returns True, it outputs the solution where the large disks of $L_1^{\prime }$ are selected. Since there are no remaining points in $V$ to cover, the remaining small disks sm$(L\setminus L_1^{\prime })$ may be selected to cover a number of points in $N$ equal to the gain of $L_1^{\prime }$. Otherwise, it concludes that there is no feasible solution with $k$ large disks.

Next, we analyze the algorithm. Consider the recursion tree $ℛ$ corresponding to Recursive-Branching$(V,\mathrm{\varnothing },1)$. We define the level of the nodes in $ℛ$ as follows. The level of the root is 1. The level of any other node is 1 plus the level of its parent. Let $L^{\ast }$ denote the large disks selected in the optimal solution. In our analysis, we assume that $L^{\ast }$ does not contain any redundant disk, i.e., removing any disk from $L^{\ast }$ leaves $V$ uncovered. If it contains such a redundant disk, then we can try our algorithm with a smaller value .

We prove the correctness of Recursive-Branching with the following lemma.

We give a reduction from Dominating set for unit disks. In this problem, we are given a set of $n$ unit disks (radius 1) $𝒟$ in the plane and a parameter $k$, and the goal is to select a subset ${𝒟}^{\prime }\subseteq 𝒟$ of $k$ disks such that for each disk $D$ in $𝒟$, $D\in {𝒟}^{\prime }$ or there is a disk $D^{\prime }$ in ${𝒟}^{\prime }$ such that $D\cap D^{\prime }\ne \mathrm{\varnothing }$.

Marx [24] proved that Dominating set for unit disks is W[1]-hard. In fact, he proved that assuming ETH, the problem cannot be solved in $f(k)\cdot n^{o(\sqrt{k})}$ time for any computable function $f$. Next, we describe our reduction.

Let $ℐ$ be the given instance of Dominating set for unit disks. Let $C$ be the set of centers of the disks in $ℐ$. The distance between a point $p$ and a set $S$ is defined as ${\min }_{q\in S}\Vert p-q\Vert$. For any point $c\in C$, let ${\delta }_c$ be the minimum distance between $c$ and the disks in $\{D(c^{\prime },2)\mid c^{\prime }\in C\text{ and }c\notin D(c^{\prime },2)\}$ (see Figure 2). Let ${\delta }_1={\min }_{c\in C}{\delta }_c$. Also, let ${\delta }_2={\min }_{c,c^{\prime }\in C}\Vert c-c^{\prime }\Vert$ with $c\ne c^{\prime }$. Denote $\delta =\min \{{\delta }_1,{\delta }_2\}$. Also, let $ϵ=\delta /6$. We set $A=C$, $P=\{(x+ϵ,y)\mid (x,y)\in C\}$, ${\rho }_1=ϵ/2$, and ${\rho }_2=2+ϵ$. Also, we use the same parameter $k$. Let ${ℐ}^{\prime }$ be the constructed instance of Par-DC-2. The construction takes ${|𝒟|}^{O(1)}$ time.