Dominating Set, Independent Set, Discrete $k$-Center, Dispersion, and Related Problems for Planar Points in Convex Position

A dominating set of $G(P)$ is a subset $S$ of vertices of $G(P)$ such that each vertex of $G(P)$ is either in $S$ or adjacent to a vertex in $S$. The dominating set problem, which seeks a dominating set of the smallest size, is a classical NP-hard problem [19, 29, 31]. In the weighted case, each point of $P$ has a weight and the problem is to find a dominating set of minimum total weight. The dominating set problem has been widely studied, with various approximation algorithms proposed [27, 55, 41, 23].

To the best of our knowledge, we are not aware of any previous work under the convex position assumption. For the unweighted case, we present an algorithm of $O(kn\log n)$ time, where $k$ is the smallest dominating set size of $G(P)$. For the weighted case, we derive an algorithm of $O(n^3{\log }^{2}n)$ time. In particular, given any $k$, our algorithm can compute in $O(k{n}^2{\log }^{2}n)$ time a minimum-weight dominating set of size at most $k$.

A closely related problem is the discrete $k$-center problem. Given a number $k$, the problem is to compute a subset of $k$ points in $P$ (called centers) such that the maximum distance between any point in $P$ and its nearest center is minimized. The problem, which is NP-hard [49], is also a classical problem with applications in clustering, facility locations, and network design. An algorithm for the dominating set problem can be used to solve the decision version of the discrete $k$-center problem: Given a value $r$ and $k$, decide whether there exists a subset of $k$ centers such that the distance from any point in $P$ to its nearest center is at most $r$. Indeed, if we define the unit-disk graph of $P$ with respect to $r$, then a dominating set of size $k$ in the graph is a discrete $k$-center of $P$ for $r$, and vice versa.

For the convex position case, we are not aware of any previous work. We propose an algorithm of $O(\min \{n^{4/3}\log n+kn{\log }^{2}n,k^{2}n{\log }^{2}n\})$ time.

An independent set of $G(P)$ is a subset of vertices such that no two vertices have an edge. The maximum independent set problem is to find an independent set of the largest cardinality. The problem of finding a maximum independent set in $G(P)$ is NP-hard [19]. Many approximation algorithms for the problem have been developed in the literature, e.g., [21, 22, 37, 38].

Under the convex position assumption, using the technique of Singireddy, Basappa, and Mitchell [47] for a dispersion problem (more details to be discussed later), one can find a maximum independent set in $G(P)$ in $O(n^6\log n)$ time. We give a new algorithm of $O(n^{7/2})$ time,¹¹1Throughout the paper, the algorithm runtime is deterministic unless otherwise stated. and another randomized algorithm of $O(n^{37/11})$ expected time using the recent randomized result of Agarwal, Ezra, and Sharir [1]. Furthermore, our algorithm can be extended to compute a maximum-weight independent set of $G(P)$ within the same time complexity when points of $P$ have weights; specifically, a maximum-weight independent set is an independent set whose total vertex weight is maximized. Since the vertices of a graph excluding an independent set form a vertex cover, our algorithm also computes a minimum-weight vertex cover of $G(P)$ in $O(n^{7/2})$ time or in randomized $O(n^{37/11})$ expected time.

Furthermore, we consider a small-size case that is to find an (unweighted) independent set of size $3$ in $G(P)$. If $P$ is not necessarily in convex position, the problem has been studied by Agarwal, Overmars, and Sharir [2], who presented an $O(n^{4/3}{\log }^{2}n)$ time algorithm. We consider the convex position case and derive an algorithm of $O(n\log n)$ time. Note that finding an independent set of size $2$ is equivalent to computing a farthest pair of points of $P$, which can be done in $O(n\log n)$ time using the farthest Voronoi diagram [45].

In addition, we consider a more general small-size case that is to find a maximum-weight independent set of size $3$ in $G(P)$ when points of $P$ have weights and are not necessarily in convex position. Our algorithm runs in $O(n^{5/3+\delta })$ time; $\delta$ refers to an arbitrarily small positive constant. Our technique can also be used to find a maximum-weight clique of size $3$ in $G(P)$ within the same time complexity. In addition, we show that a maximum-weight independent set or clique of size $2$ can be found in $n^{4/3}{2}^{O({\log }^{\ast }n)}$ time. All these algorithms also work for computing the minimum-weight independent set or clique. We are not aware of any previous work on these weighted problems. As mentioned above, the problem of finding an (unweighted) independent set of size $3$ can be solved in $O(n^{4/3}{\log }^{2}n)$ time [2]. It is also known that finding an (unweighted) clique of size $3$ in a disk graph (not necessarily unit-disk graph) can be done in $O(n\log n)$ time [30].

A related problem is the dispersion problem (also called maximally separated set problem [2]). Given $P$ and a number $k$, we wish to find a subset of $k$ points from $P$ so that their minimum pairwise distance is maximized. The problem is NP-hard [50]. An algorithm for the independent set problem of $G(P)$ can be used as a decision algorithm for the dispersion problem: Given a value $r$, we can decide whether $P$ has a subset of $k$ points whose minimum pairwise distance is larger than $r$ using the independent set algorithm (i.e., by defining an edge for two points in the graph if their distance is at most $r$).

Under the convex position assumption, Singireddy, Basappa, and Mitchell [47] previously gave an $O(n^4{k}^2)$ time algorithm for the problem. Using our independent set algorithm as a decision procedure and doing binary search among the interpoint distances of $P$, we present a new algorithm that can solve the problem in $O(n^{7/2}\log n)$ time, or in randomized $O(n^{37/11}\log n)$ expected time. For a special case where $k=3$, the algorithm of [2] solves the problem in $O(n^{4/3}{\log }^{3}n)$ time even if the points of $P$ are not in convex position. Our new algorithm, which works on the convex-position case only, runs in $O(n{\log }^{2}n)$ time. This is achieved using parametric search [20, 39] with our independent set algorithm as a decision algorithm. In addition, with our decision algorithm and Chan’s randomized technique [11], we can obtain a randomized algorithm of $O(n\log n)$ expected time. We note that a recent work [35] proposed another algorithm of $O(n^2)$ time, apparently unaware of the result in [2].

The rest of the paper is organized as follows. After introducing notation in Section 2, we present our algorithms for the dominating set, the discrete $k$-center, the independent set, and the dispersion problems for points in convex position in Sections 3, 4, 5 and 6, respectively. As the only problem for points in arbitrary position studied in this paper, the size-3 weighted independent set problem is discussed in Section 7. Due to the space limit, many details and proofs are omitted but can be found in the full paper.

First of all, notice that the first two properties imply the last three. Therefore, it suffices to prove the first two properties.

Let $S_1$ (resp., $S_2$) be the subset of centers of $S\setminus \{p_i,p_j\}$ that have a sublist in $P(i,j)$ (resp., $P(j,i)$). By Lemma 3, each center of $S_1$ has at most one sublist in $P(i,j)$ and each center of $S_2$ has at most one sublist in $P(j,i)$. We add $p_i$ and $p_j$ to both $S_1$ and $S_2$. We sort all centers of $S_1$ as a sequence (called the sorted sequence of $S_1$) by the points of their sublists appearing in $P[i,j]$ from $p_i$ to $p_j$ (and thus $p_i$ is the first center and $p_j$ is the last one in the sequence). Similarly, we sort all centers of $S_2$ as a sequence (called the sorted sequence of $S_2$) by the points of their sublists appearing in $P[j,i]$ from $p_i$ to $p_j$ (and thus $p_i$ is the first center and $p_j$ is the last one in the sequence). To prove the first two properties of the lemma, it suffices to show the following statement: There exists an ordering of $S$ such that (1) $p_i$ is the first one in the ordering and $p_j$ is the last one; (2) the sorted sequence of $S_1$ (resp., $S_2$) is a subsequence of the ordering.

We say that two centers $p_{j_1},p_{j_2}\in S$ are conflicting if $p_{j_1}$ appears in front of $p_{j_2}$ in the sorted sequence of $S_1$ while $p_{j_2}$ appears in front of $p_{j_1}$ in the sorted sequence of $S_2$. It is not difficult to see that if no two centers of $S$ are conflicting then the above statement holds. Assume to the contrary that there exist two centers $p_{j_1},p_{j_2}\in S$ that are conflicting. Then, since the two centers are in both $S_1$ and $S_2$, each of them has two sublists. Since they are conflicting, by the definition of the sorted sequences of $S_1$ and $S_2$ and due to the convexity of $P$, the group of $p_{j_1}$ cannot be separated from the group of $p_{j_2}$ by a line, a contradiction with the line separable property of $\varphi$. $◀$

We begin by introducing the following definition.

For a subset $P^{\prime }\subseteq P$, let $𝒟(P^{\prime })$ denote the union of the unit disks centered at the points of $P^{\prime }$. Note that a subset $S\subseteq P$ is a dominating set if and only if $P\subseteq 𝒟(S)$.

Our algorithm has $k$ iterations. In each $t$-th iteration with $1\le t\le k$, we compute a set ${ℒ}_t$ of $O(n^2)$ sublists of $P$, and each sublist $L\in {ℒ}_t$ is associated with a weight $w^{\prime }(L)$ and a set $S_L\subseteq P$ of at most $t$ points. Our algorithm maintains the following invariant: For each sublist $L\in {ℒ}_t$, $w(S_L)\le w^{\prime }(L)$ and points of $L$ are all covered by $𝒟(S_L)$. Suppose that there exists a set $S\subseteq P$ of $k$ points such that $P\subseteq 𝒟(S)$. Then we will show that ${ℒ}_k$ contains a sublist $L$ that is $P$ and $w^{\prime }(L)\le W^{\ast }$. As such, after $k$ iterations, we only need to find all sublists of ${ℒ}_k$ that are $P$ and then return the one with the minimum weight.

In the first iteration, for each point $p_i\in P$, we compute the two indices $a_i^i$ and $b_i^i$; we show in Lemma 7 that this can be done in $O(\log n)$ time after $O(n\log n)$ time preprocessing. Then, let ${ℒ}_1=\{P(b_i^i,a_i^i)|p_i\in P\}$. For each sublist $L=P(b_i^i,a_i^i)$ of ${ℒ}_1$, we set $S_L=\{p_i\}$ and $w^{\prime }(L)=w_i$. Clearly, the algorithm invariant holds on all sublists of ${ℒ}_1$. This finishes the first iteration. Although $|{ℒ}_1|=O(n)$, as will be seen next, $|{ℒ}_t|=O(n^2)$ for all $t\ge 2$.

In general, suppose that we have a set ${ℒ}_{t-1}$ of $O(n^2)$ sublists and each sublist $L\in {ℒ}_{t-1}$ is associated with a weight $w^{\prime }(L)$ and a set $S_L\subseteq P$ of at most $t-1$ points such that the algorithm invariant holds, i.e., $w(S_L)\le w^{\prime }(L)$ and points of $L$ are all covered by $𝒟(S_L)$. We now describe the $t$-th iteration of the algorithm.

For each point $p_i\in P$, we perform a counterclockwise processing procedure as follows. For each point $p_j\in P$, we do the following. Compute the minimum weight sublist from ${ℒ}_{t-1}$ that contains $P[a_i^i,j]$; we call this step a minimum-weight enclosing sublist query. We show later that each such query can be answered in $O({\log }^{2}n)$ time after $O(n^2\log n)$ time preprocessing on the sublists of ${ℒ}_{t-1}$. Let $P[j_{i1},j_{i2}]$ be the sublist computed above. Then, we compute the index $a_i^{j_{i2}+1}$. By definition, the union of the following three sublists is a sublist of $P$: $P(b_i^i,a_i^i)$, $P[j_{i1},j_{i2}]$, and $P(j_{i2},a_i^{j_{i2}+1})$; denote by $L$ the sublist. We set $S_L=S_{L^{\prime }}\cup \{p_i\}$ and $w^{\prime }(L)=w^{\prime }(L^{\prime })+w_i$, where $L^{\prime }=P[j_{i1},j_{i2}]$. We add $L$ to ${ℒ}_t$. We next argue that the algorithm invariant holds for $L$, i.e., points of $L$ are covered by $𝒟(S_L)$, $|S_L|\le t$, and $w(S_L)\le w^{\prime }(L)$. Indeed, by definition, all the points of $P(b_i^i,a_i^i)\cup P(j_{i2},a_i^{j_{i2}+1})$ are covered by the disk $D_{p_i}$. Since the sublist $L^{\prime }$ is from ${ℒ}_{t-1}$, by our algorithm invariant, $L^{\prime }$ is covered by $𝒟(S_{L^{\prime }})$, $|S_{L^{\prime }}|\le t-1$, and $w(S_{L^{\prime }})\le w^{\prime }(L^{\prime })$. Therefore, $L$ is covered by $𝒟(S_{L^{\prime }}\cup \{p_i\})$ and $|S_L|\le t$. In addition, we have $w(S_L)\le w(S_{L^{\prime }})+w_i\le w^{\prime }(L^{\prime })+w_i=w^{\prime }(L)$. As such, the algorithm invariant holds on $L$.

The above counterclockwise processing procedure for $p_i$ will add $O(n)$ sublists to ${ℒ}_t$. Symmetrically, we perform a clockwise processing procedure for $p_i$, which will also add $O(n)$ sublists to ${ℒ}_t$. We briefly discuss it. Given $p_i\in P$, for each point $p_j\in P$, we compute the minimum weight sublist from ${ℒ}_{t-1}$ that contains $P[j,b_i^i]$. Let $P[j_{i3},j_{i4}]$ be the sublist computed above. Then, we compute the index $b_i^{j_{i3}-1}$. Let $L$ be the sublist that is the union of the following three sublists: $P(b_i^i,a_i^i)$, $P[j_{i3},j_{i4}]$, and $P(b_i^{j_{i3}-1},j_{i3})$. We let $S_L=S_{L^{\prime }}\cup \{p_i\}$ and $w^{\prime }(L)=w^{\prime }(L^{\prime })+w_i$, where $L^{\prime }=P[j_{i3},j_{i4}]$. As above, the algorithm invariant holds on $L$. We add $L$ to ${ℒ}_t$. In this way, the $t$-th iteration computes $O(n^2)$ sublists in ${ℒ}_t$.

After the $k$-th iteration, we find from all sublists of ${ℒ}_k$ that are $P$ the one $L^{\ast }$ whose weight $w^{\prime }(L^{\ast })$ is the minimum. Based on the ordering property in Lemma 4, the next lemma shows that $S_{L^{\ast }}$ is an optimal dominating set.

In each iteration, we perform $O(n^2)$ operations for computing indices $a_i^j$ and $b_i^j$, and perform $O(n^2)$ minimum-weight enclosing sublist queries. We show later that each query takes $O({\log }^{2}n)$ time after $O(n^2\log n)$ time preprocessing. As such, each iteration of the algorithm takes $O(n^2{\log }^{2}n)$ time and the total time of the algorithm is thus $O(k{n}^2{\log }^{2}n)$.

The following lemma provides a data structure for computing the indices $a_i^j$ and $b_i^j$.

Given a set $ℒ$ of $m$ sublists of $P$, each sublist has a weight. We wish to build a data structure to answer the following minimum-weight enclosing sublist queries: Given a sublist $L$, compute the minimum weight sublist of $ℒ$ that contains $L$. We have the following lemma.

Theorem 9 summarizes our result. Applying Theorem 9 with $k=n$ leads to Corollary 10.

We follow the iterative algorithmic scheme of the weighted case, but incorporate a greedy strategy using the property that all points of $P$ have the same weight.

In each $t$-th iteration of the algorithm, $t\ge 1$, we compute a set ${ℒ}_t$ of $O(n)$ sublists and each list $L\in {ℒ}_t$ is associated with a set $S_L\subseteq P$ of at most $t$ points. Our algorithm maintains the following invariant: For each sublist $L\in {ℒ}_t$, all points of $L$ are covered by $𝒟(S_L)$, i.e., the union of the unit disks centered at the points of $S_L$. If $k$ is the smallest dominating set size, we show in Lemma 11 that after $k$ iterations, ${ℒ}_k$ is guaranteed to contain a sublist that is $P$. Thus, we can stop the algorithm as soon as the first sublist that is $P$ is computed.

Initially, we compute the indices $a_i^i$ and $b_i^i$ for all points $p_i\in P$. By Lemma 7, this takes $O(\log n)$ time after $O(n\log n)$ time preprocessing. In the first iteration, we have ${ℒ}_1=\{P(b_i^i,a_i^i)|p_i\in P\}$. For each sublist $L=P(b_i^i,a_i^i)\in {ℒ}_1$, we set $S_L=\{p_i\}$. Clearly, the algorithm invariant holds.

In general, suppose that we have a set ${ℒ}_{t-1}$ of $O(n)$ sublists such that the algorithm invariant holds. We assume that no sublist of ${ℒ}_{t-1}$ is $P$. Then, the $t$-th iteration of the algorithm works as follows. For each point $p_i\in P$, we perform the following counterclockwise processing procedure. We first compute the sublist of ${ℒ}_{t-1}$ that contains $p_{a_i^i}$ and has the most counterclockwise endpoint. This is done by a counterclockwise farthest enclosing sublist query. We show later in Section 3.3 that each such query takes $O(\log n)$ time after $O(n\log n)$ time preprocessing for ${ℒ}_{t-1}$. Let $P[j_{i1},j_{i2}]$ be the sublist computed above. Then, we compute the index $a_i^{j_{i2}+1}$ in $O(\log n)$ time by Lemma 7. Note that the union of the following three sublists is a sublist $L$ of $P$: $P(b_i^i,a_i^i)$, $P[j_{i1},j_{i2}]$, and $P(j_{i2},a_i^{j_{i2}+1})$. We add $L$ to ${ℒ}_t$ and set $S_L=S_{L^{\prime }}\cup \{p_i\}$ with $L^{\prime }=P[j_{i1},j_{i2}]$. By our algorithm invariant, points of $L^{\prime }$ are covered by $𝒟(S_{L^{\prime }})$. By definition, points of $P(b_i^i,a_i^i)\cup P(j_{i2},a_i^{j_{i2}+1})$ are covered by $D_{p_i}$. Therefore, all points of $L$ are covered by $𝒟(S_L)$. Hence, the algorithm invariant holds for $L$. In addition, if $L$ is $P$, we stop the algorithm and return $S_L$ as an optimal dominating set.

Symmetrically, we perform a clockwise processing procedure for $p_i$. We compute the sublist from ${ℒ}_{t-1}$ that contains $b_i^i$ and has the most clockwise endpoint; this is done by a clockwise farthest enclosing sublist query. Let $P[j_{i3},j_{i4}]$ be the sublist computed above. Then, we compute the index $b_i^{j_{i3}-1}$. Let $L$ be the sublist that is the union of the following three sublists: $P(b_i^i,a_i^i)$, $P[j_{i3},j_{i4}]$, and $P(j_{i3},b_i^{j_{i3}-1})$. Let $S_L=S_{L^{\prime }}\cup \{p_i\}$ with $L^{\prime }=P[j_{i3},j_{i4}]$. As above, the algorithm invariant holds on $L$. We add $L$ to ${ℒ}_t$. If $L$ is $P$, then we stop the algorithm and return $S_L$ as an optimal dominating set.

The following lemma proves the correctness of the algorithm.

In each iteration, we perform $O(n)$ operations for computing indices $a_i^j$ and $b_i^j$ and $O(n)$ counterclockwise/clockwise farthest enclosing sublist queries. Computing indices $a_i^j$ and $b_i^j$ takes $O(\log n)$ time by Lemma 7. We show in Lemma 12 that each counterclockwise/clockwise farthest enclosing sublist query can be answered in $O(\log n)$ time after $O(n\log n)$ time preprocessing. As such, each iteration runs in $O(n\log n)$ time and the total time of the algorithm is $O(kn\log n)$, where $k$ is the smallest dominating set size.

It remains to describe the data structure for answering counterclockwise/clockwise farthest enclosing sublist queries. We only discuss the counterclockwise case as the clockwise case can be handled analogously. Given a set $ℒ$ consisting of $n$ sublists of $P$, the goal is to build a data structure to answer the following counterclockwise farthest enclosing sublist queries: Given a point $p\in P$, find a sublist in $ℒ$ that contains $p$ with the farthest counterclockwise endpoint from $p$. We have the following lemma.

We conclude with the following theorem and corollary, which will be used in Section 4 to solve the discrete $k$-center problem.

We redefine the unit-disk graph of $P$ with a parameter $r$, where two points in $P$ are connected by an edge if their distance is at most $r$. We then apply the algorithm of Theorem 13. If the algorithm finds a sublist $L$ that is $P$ within $k$ iterations, then we return $S=S_L$; otherwise such a subset $S$ as in the lemma statement does not exist. Since we run the algorithm for at most $k$ iterations, the total time of the algorithm is $O(kn\log n)$. $◀$