Single-Criteria Metric $𝒓$-Dominating Set Problem via Minor-Preserving Support

Geometric set cover problems have their own history and success [7, 16, 17, 62]. Notably, for an unweighted set cover instance $(X,ℛ)$, the result of Brönnimann and Goodrich [7] provided a recipe to achieve $O(1)$-approximation. Their pioneering use of multiplicative weight update algorithm requires the existence of small $\epsilon$-net: First, find an $\epsilon$-net $N$ for the dual set system $(ℛ,X)$ (notice that here the $\epsilon$-net is in the dual and thus a subset of ranges in $ℛ$). If there are element $x$ in $X$ not covered by $N$, double the weight of every range in $ℛ$ that covers $x$, to increase the chance of choosing one such range in the next round. As a result, by setting $\epsilon =\mathrm{\Theta }(1/\mathrm{opt})$, this implies an $O(g(\mathrm{opt}))$-approximation for any set cover instance, given the dual system has an $\epsilon$-net of size $O(\frac{1}{\epsilon }\cdot g(\frac{1}{\epsilon }))$. (See [24] for an LP interpretation and a simpler proof.)

For set system of bounded VC-dimension [61], there is always an $\epsilon$-net of size $O(\frac{1}{\epsilon }\log \frac{1}{\epsilon })$ [36]. Also, if the VC-dimension of a primal system is $d$, then the dual system has VC-dimension at most $2^d$ [34]. To get $O(1)$-approximation, however, we need a much stronger assumption of $O(\frac{1}{\epsilon })$-size $\epsilon$-net in the dual system. This is not always achievable even for simple geometric shapes like lines and rectangles [49]; in fact, among the basic geometric shapes, only a handful are known to have linear-size $\epsilon$-net, including halfspaces in 2D and 3D [46, 51, 45], unit-cubes in 3D [17], and family of pseudodisks in the plane (both primal and dual) [53].

For our application of unbounded $r$-dominating set problem, the “geometric shapes” are the radius-$r$ balls in planar graphs, which is discrete in nature, lacking well-defined boundary curves to even make the definition of pseudodisks meaningful. One might sneer at the issue and say, “there must be a way; how can distance balls in the plane be much different from pseudodisks?” But even if we redefine the notion of pseudodisks combinatorially (for every pair of regions $A$ and $B$, all three sets $A\cap B$, $A\setminus B$, and $B\setminus A$ are connected), the distance balls are still not pseudodisk. In fact, they can be piercing in the sense of Raman-Ray [54], as illustrated by Figure 1.

Fortunately, Pyrga and Ray [53] provided an alternative method to obtain linear-size $\epsilon$-net (in the dual) – to construct a sparse support for the primal system $(X,ℛ)$. We say a set system $(X,ℛ)$ has a support, if for any subsystem $(X^{\prime },{ℛ}_{|X^{\prime }})$ of $(X,ℛ)$, there is an undirected graph $H$ on the elements of $X^{\prime }$ such that for every set $R$ in ${ℛ}_{|X^{\prime }}$, the subgraph $H_R$ of $H$ induced by the elements of $R$ is connected. The support is sparse if every such graph $H$ is sparse. The work of Pyrga and Ray [53] implies that if $(X,ℛ)$ has bounded VC-dimension and a sparse support, then the dual system $(X,ℛ)$ has $\epsilon$-net of size $O(\frac{1}{\epsilon })$.

Our first technical contribution is to compute a support for any collection of distance balls in any arbitrary graph (not just planar graphs). Crucially, if the given graph is planar, then so is the support. We remind the reader that our original goal is to solve the $r$-dominating set problem with unbounded $r$; thus the construction of the support has to hold for balls of unbounded radii as well. This is the first construction of its kind; most previous work on sparse support focus on geometric shapes, and almost entirely restricted to planar support for set systems that are pseudodisks [53] and their generalizations [54]. For piercing systems like axis-parallel rectangles, there are configurations where no planar support can exist [52].

Instead of focusing on planarity, we shift the narrative by arguing that a support graph for $(X,ℛ)$ is really a connectivity sketch that exists for every graph $G$ on $X$, as long as the sets in $ℛ$ are distance balls on $G$. Our construction for support on arbitrary balls in $G$ can be described simply as follows: Build a Voronoi diagram of $V(G)$ with respect to balls centers, then contract every Voronoi cell into a single node. We argue that the contracted graph is a support of $G$. (The benefit of this additional property becomes evident when we tackle the next challenge.) Both planarity and sparseness come as a byproduct of the fact that contraction of the Voronoi diagram is a minor of $G$. (See Theorem 2 for a precise statement.) (A similar Voronoi diagram idea can be found in the work of Le [42, 26]; but their version only enables single-criteria algorithm for unweighted metric $r$-dominating set problem.)

There is another, perhaps more severe, obstacle to overcome. We want to solve the weighted version of the $r$-dominating set problem. The Brönnimann-Goodrich MWU approach relies on computing regular $\epsilon$-net (as subset of balls covering the vertices); the size bound on $\epsilon$-net translates to approximation guarantee on size of the cover, and thus can only work in the unweighted setting. Varadarajan [63] extended the $\epsilon$-net idea to the weighted setting. This quasi-uniformity sampling technique computes $\epsilon$-nets that samples each set in $ℛ$ with (roughly) equal probability, which then can be made aware of the weights on $ℛ$. Chan, Grant, Könemann, and Sharpe [11] later polished this technique and made connection to a more refined measure on set systems called shallow cell complexity. In our context, cell complexity refers to the number of different equivalent classes (called cells) of points that are covered by the same subset of $r$-balls. We say a cell has depth $k$ if the points within are covered by up to $k$ balls. A set system has shallow cell complexity $f(|ℛ|,k)$ if the number of cells of depth at most $k$ is bounded by $f(|ℛ|,k)$; for the purpose of obtaining $O(1)$-approximation for set cover, one requires the shallow cell complexity to be $O(|ℛ|\cdot \mathrm{poly}k)$.

The quasi-uniformity sampling technique can be used to solve the constant $r$ case for weighted $r$-dominating set problem on minor-free graphs (and graphs with bounded expansion as well [20]). This is because in the case of constant radius $r$, the whole cell complexity is linearly bounded [57, 38], which directly bounds the shallow counterpart. Unfortunately, it is known that the cell complexity of $r$-balls on a planar graph can be cubic in $r$ [38], and thus cannot help in the unbounded $r$ setting.

One way to see why halfspaces and pseudodisks are special is that they both have linear union complexity [40, 17]. Application of the classical Clarkson-Shor technique then implies that the shallow cell complexity is bounded by $O(|ℛ|\cdot k)$. When working with arbitrary-radius balls on graphs however, we run into trouble applying Clarkson-Shor. First, there is no well-defined notion of union complexity for a collection of subgraphs. One would imagine the support can take the role as the linear-size object at the base case for Clarkson-Shor; but this intuition is insufficient. The main issue is that for pseudodisks, the number of cells can be charged to the complexity of the whole pseudodisk arrangement by Euler’s formula, and every crossing in the arrangement is uniquely defined by two pseudodisks. There is no immediate equivalent object for distance balls that allows for such counting.

Our solution is to reimagine the unique representative argument by Raman and Ray for the non-piercing family [55]; the new proof is substantially different and relies on geometric properties of distance balls, instead of topological properties of curve sweeping [55, §6]. First we argue that every cell can be charged to a unique 3-tuple of ball centers (Lemma 7). This allows us to apply Clarkson-Shor and reduce the problem to counting cells of depth 1, 2, and 3. Depth 1 and 2 are straightforward; for depth-3 cells, we exploit the additional property that our support for distance balls came from contracting Voronoi cells with respect to the ball centers, and thus the number of depth-3 cells can be counted towards the complexity of the Voronoi diagram, which is asymptotically the same as the planar support (Lemma 13).

Assume the contrary. Then, there is some vertex $v^{\prime }$ which is contained within some ball $D_3$ such that $v\notin D_3$. By definition of $\alpha$ and $\beta$, it must be that the center of $D_3$ is closer to $v^{\prime }$ than $D_1$ and $D_2$. However, since $v^{\prime }$ is either in $\pi (c_{D_1},v)$ or $\pi (c_{D_2},v)$, this means that $D_3$ is closer to $v$ than one of $D_1$ or $D_2$, and thus $D_3$ must contain $v$, a contradiction by the assumption that all balls have equal radius. (See Figure 4.) $◀$

The third component of our encoding, $\gamma$, can now be defined. For $k=3$, $\gamma$ is simply the remaining ball after removing $\alpha$ and $\beta$. For $k\ge 4$, we define $\gamma$ procedurally after fixing $\alpha ,\beta$. Denote the set of all cells of depth $k$ with $\alpha (v_c)=D_1$ and $\beta (v_c)=D_2$ as $C_k(D_1,D_2)$. We additionally collect the representatives $v_c$ of each $c\in C_k(D_1,D_2)$ into a corresponding set $V_k(D_1,D_2)$. Let $T_D(S)$ be the shortest path tree from the center $x_D$ of a ball $D$ to a set of vertices $S$. Consider the shortest path tree $T_{D_1}(V_k(D_1,D_2))$. We will process all $v_c\in V_k(D_1,D_2)$ using the plane drawing of $T_{D_1}(V_k(D_1,D_2))$.

Perform a depth-first traversal starting at $x_D$, processing children in clockwise order. The depth-first traversal $T_{D_1}(V_k(D_1,D_2))$ of gives a total ordering of the vertices in $V_k(D_1,D_2)$, which also induces a total ordering $\sigma$ on the corresponding cells $C_k(D_1,D_2)$. For brevity, we will index the cells based on their order in $\sigma$ (the $i$th cell as $c_i$) in a cyclic manner. For the $i$th cell $c_i$ in the total ordering, we assign $\gamma (c_i)$ to be an arbitrary ball $D$ with $D\in \mathrm{ℎ𝑖𝑡}(v_{c_i})$ and $D\notin \mathrm{ℎ𝑖𝑡}(v_{c_{i-1}})$. Since $|\mathrm{ℎ𝑖𝑡}(v_{c_i})|=|\mathrm{ℎ𝑖𝑡}(v_{c_i-1})|=k$ and $\mathrm{ℎ𝑖𝑡}(v_{c_i})\ne \mathrm{ℎ𝑖𝑡}(v_{c_i-1})$ (by the definition of cell), such a $D$ must always exist, and thus we can assign $\gamma (c_i)$ to all cells.

We now show that this definition of $\gamma$ is sufficient to ensure that each distinct cell $c$ of size $k$ has a unique encoding. First, we use Lemma 5 to show that the representative vertices of cells with the same $\alpha$ and $\beta$ cannot form ancestor relationships in $T_{D_1}(V_k(D_1,D_2))$.

First consider $T_{D_1}(V_k(D_1,D_2)$. If $v_c$ were an ancestor of $v_{c^{\prime }}$, then $v_c$ would be in $\pi (D_1,v_{c^{\prime }})$. This would imply that $\mathrm{ℎ𝑖𝑡}(v_{c^{\prime }})\subseteq \mathrm{ℎ𝑖𝑡}(v_c)$ by Lemma 5. However, since $c$ and $c^{\prime }$ have depth $k$, $|\mathrm{ℎ𝑖𝑡}(v_c)|=|\mathrm{ℎ𝑖𝑡}(v_{c^{\prime }})|=k$. The subset relationship would hence require that $\mathrm{ℎ𝑖𝑡}(v_c)=\mathrm{ℎ𝑖𝑡}(v_{c^{\prime }})$, and thus $c$ and $c^{\prime }$ are the same class, which is a contradiction. A symmetric argument applies for $T_{D_2}(V_k(D_1,D_2)$. $◀$

This means that for any $c,c^{\prime }$ with the same $\alpha$ and $\beta$, $\pi (\alpha (v_c),v_c)⊈\pi (\alpha (v_c),v_{c^{\prime }})$.

If two cells have the same depth and $\alpha$ and $\beta$, they are both indexed by the same traversal order $\sigma$. Consider two cells $c_i,c_j$ such that $⟨\alpha (c_i),\beta (c_i),\gamma (c_i)⟩=⟨\alpha (c_j),\beta (c_j),\gamma (c_j)⟩=(D_1,D_2,D_3)$ and $|\mathrm{ℎ𝑖𝑡}(v_{c_i})|=|\mathrm{ℎ𝑖𝑡}(v_{c_j})|=k$.

We need to consider how $c_i$ and $c_j$ were assigned the same $\gamma$. Recall that we force adjacent cells $c_{i-1},c_i$ to not just have different $\gamma$ assignments, but that the $\gamma (c_i)$ not contain $\gamma (c_{i-1})$. This forces $v_{c_{i-1}}$ and $v_{c_{j-1}}$ to not be contained by $D_3$. Let $a$ be the lowest common ancestor of $v_{c_{i-1}}$ and $v_{c_{j-1}}$ in $T_{D_1}(V_k(D_1,D_2)$. Similarly, let $b$ be the lowest common ancestor of $v_{c_{i-1}}$ and $v_{c_{j-1}}$ in $T_{D_2}(V_k(D_1,D_2)$. We consider the cycle $F$ formed by the union of the following shortest paths: $\pi (a,v_{c_{i-1}})$ to $\pi (v_{c_{i-1}},b)$ to $\pi (b,v_{c_{j-1}})$ to $\pi (v_{c_{j-1}},a)$. Since $G$ is planar, $F$ describes the boundary of some region $R(F)$. Since , by the definition of our traversal one of $v_{c_i}$ or $v_{c_j}$ lies in $R(F)$ and the other lies outside. (We give an example $R(F)$ as a gray region in Figure 5.) This means that, for $D_3$ to contain both $v_{c_i}$ and $v_{c_j}$, $D_3$ must also contain some vertex $u^{\prime }$ of $F$. Assume WLOG that $u^{\prime }$ lies on $\pi (D_3,v_{c_j})$. Since $u^{\prime }$ lies on $F$, it must be on one of $\pi (D_1,v_{c_{i-1}}),\pi (D_1,v_{c_{j-1}}),\pi (D_2,v_{c_{i-1}}),$ or $\pi (D_2,v_{c_{i-1}})$.

• $\mathrm{■}$

  If $u^{\prime }$ is in $\pi (D_1,v_{c_{i-1}})$ or $\pi (D_1,v_{c_{j-1}})$, then we know that $D_3$ must be further from $u^{\prime }$ than $D_1$ since $D_3$ cannot contain $v_{c_{i-1}}$ or $v_{c_{j-1}}$. However, since $\alpha (v_{c_j})=D_1$, $D_3$ must be closer to $u^{\prime }$ than $D_1$ since $u^{\prime }$ is on $\pi (D_3,v_{c_j})$ and $\alpha (v_{c_j})$ is the furthest ball from $v_{c_j}$ which still contains it. (See left subfigure of Figure 5.)

• $\mathrm{■}$

  Similarly, if $u^{\prime }$ is in $\pi (D_2,v_{c_{i-1}})$ or $\pi (D_2,v_{c_{j-1}})$, then $D_3$ must be further from $u^{\prime }$ than $D_2$ since $D_3$ cannot contain $v_{c_{i-1}}$ or $v_{c_{j-1}}$. However, since $\beta (v_{c_j})=D_2$, $D_3$ must be closer to $u^{\prime }$ than $D_2$ since $u^{\prime }$ is on $\pi (D_3,v_{c_j})$ and $\beta (v_{c_j})$ is the second furthest ball from $v_{c_j}$, while $D_3$ is at best third furthest. (See right subfigure of Figure 5.)

We get a contradiction in both cases, which means that $\gamma (c_i)$ cannot equal $\gamma (c_j)$, and thus every cell $c$ of the same depth $k\ge 3$ must have a unique encoding $⟨\alpha (c),\beta (c),\gamma (c)⟩$. $◀$

For any $v^{\prime \prime }\in \pi (v^{\prime },v)$, because $v^{\prime }$ is between $x_D$ and $v^{\prime \prime }$ on $\pi (x_D,v)$, $d(x_D,v^{\prime \prime })=d(x_D,v^{\prime })+d(v^{\prime },v^{\prime \prime })$. We also know that $d(x_{D^{\prime }},v^{\prime \prime })\le d(x_{D^{\prime }},v^{\prime })+d(v^{\prime },v^{\prime \prime })$. Since $d(x_{D^{\prime }},v^{\prime })\le d(x_D,v^{\prime })$, we can simply plug in to get $d(x_{D^{\prime }},v^{\prime \prime })\le d(x_D,v^{\prime })+d(v^{\prime },v^{\prime \prime })=d(x_D,v^{\prime \prime })$. $◀$

Consider a ball $D^{\prime }\notin \mathrm{ℎ𝑖𝑡}(v_c)$ for which a vertex $v$ of $\pi (x_D,v_c)$ lies in the Voronoi cell $F_D$. If this is the case, then all the vertices after $v$ in $\pi (x_D,v_c)$ will be closer to $D^{\prime }$ than they are to $D$, and since $D$ contains $v_c$, $D^{\prime }$ must also then contain $v_c$, which is a contradiction. $◀$

This means that the shortest paths from the centers of the balls hit by $v_c$ to the vertex $v_c$ must stay within the Voronoi cells of $\mathrm{ℎ𝑖𝑡}(v_c)$. This observation, paired with Lemma 8, allows us to define $\mathrm{𝑏𝑎𝑠𝑒}(v_c)$ based on $\pi (x_{\alpha (v_c)},v_c)$. We consider two cases:

• $\mathrm{■}$

  Case 1: Some vertex $v$ in $\pi (x_{\alpha (v_c)},v_c)$ lies in $F_{\beta (v_c)}$. Assign $\mathrm{𝑏𝑎𝑠𝑒}(v_c)\leftarrow \beta (v_c)$.

• $\mathrm{■}$

  Case 2: No vertex $v$ in $\pi (x_{\alpha (v_c)},v_c)$ lies in $F_{\beta (v_c)}$. Assign $\mathrm{𝑏𝑎𝑠𝑒}(v_c)\leftarrow \gamma (v_c)$.

Now that we have assigned every cell to a ball, we consider a ball $D$ and the set $\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)$, which is the set of cells $c$ with $\mathrm{𝑏𝑎𝑠𝑒}(c)=D$. We will consider the cells of $\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)$ in relation to the neighbors of $D$ within the Voronoi partition graph $H$.

If cell $c$ is a case-1 cell, we have that a vertex $v$ in $\pi (x_{\alpha (v_c)},v_c)$ which lies in $F_{\beta (v_c)}$. By Lemma 8, no vertex of $\pi (v,v_c)$ can lie in $F_{\alpha (v_c)}$. Additionally, $v_c$ must lie in $F_{\gamma (v_c)}$ by definition of $\alpha$ and $\beta$. Let $u$ be the first vertex of $\pi (v,v_c)$ which lies in $F_{\gamma (v_c)}$. Let $v^{\prime }$ be last vertex of ${\pi }_{\alpha ,\beta }(v_c)$ which lies in $F_{\alpha (v_c)}$. The subwalk ${\pi }_{\alpha ,\beta }(v_c)[v^{\prime },u]$ satisfies this condition.

If cell $c$ is a case-2 cell, we have no such vertex and $\pi (x_{\alpha (v_c)},v_c)$ lies entirely in $\alpha (v_c)$ or $\gamma (v_c)$. Let $u$ be the last vertex of $\pi (x_{\alpha (v_c)},v_c)$ which lies in $F_{\alpha (v_c)}$ and let $u^{\prime }$ be the last vertex of $\pi (x_{\beta (v_c)},v_c)$ that lies in $F_{\beta (v_c)}$. We then can take our subpath to be ${\pi }_{\alpha ,\beta }(v_c)[u,u^{\prime }]$, and this will satisfy the condition. $◀$

We now consider the neighbors of $D$ in the Voronoi support $H$, $N_H(D)$. In Lemma 10, the subwalk ${\pi }_c$ of cell $c$ in $\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)$ runs between the two balls of $\mathrm{ℎ𝑖𝑡}(v_c)\setminus D$, both of which must be in $N_H(D)$ since $H$ is simply the contraction of the Voronoi partition of $G$. We can now define a graph $G_D$ on $N_H(D)$ to count the number of cells in $\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)$. For every cell $c$ of $\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)$, add an edge $e_c$ between the balls of $\mathrm{ℎ𝑖𝑡}(v_c)\setminus D$. Since the underlying graph $G$ is planar, we can sketch a drawing of $G_D$ as follows:

To draw the curve ${\zeta }_c$ corresponding to cell $c$ of $\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)$, we first consider the subpath ${\pi }_c$ that we get from Lemma 10, using a plane drawing of $G_D$. Let $v$ be the first endpoint of ${\pi }_c$ lying in a ball $D_1$ and $v^{\prime }$ be the second endpoint of ${\pi }_c$ lying in a ball $D_2$. We first draw the center $x_{D_1}$ in its location on any plane drawing of the underlying graph $G$. We then sketch ${\zeta }_c$ on $\pi (x_{D_1,v})$. This is followed by sketching ${\pi }_c$, and then finally sketching the walk $\pi (v^{\prime },x_{D_2})$. Since this sketch is over a path, we will refer to this walk in $G$ as $\pi ({\zeta }_c)$.

Let $e_c=(D_1,D_2)$ and $e_{c^{\prime }}=(D_3,D_4)$. For $c$ $(c^{\prime })$, the common vertex $v$ must lie on a shortest path from either $x_{D_1}$ or $x_{D_2}$ ($x_{D_3}$ or $x_{D_4}$) to $v_c$ ($v_{c^{\prime }}$) by construction. Without loss of generality, assume $x_{D_1}$ and $x_{D_3}$. One of $x_{D_1}$ or $x_{D_3}$ must be at least as close as the other to $v_c$. Without loss of generality, assume $x_{D_1}$. By Lemma 8, this implies that $D_1$ contains $v_{c^{\prime }}$, and is thus in $\mathrm{ℎ𝑖𝑡}(v_{c^{\prime }})$. We know that $D$ is contained within $\mathrm{ℎ𝑖𝑡}(v_{c^{\prime }})$, as we only ever assign $\mathrm{𝑏𝑎𝑠𝑒}(v_{c^{\prime }})$ to a member of $\mathrm{ℎ𝑖𝑡}(v_{c^{\prime }})$. Thus, in order for $c^{\prime }$ to be depth 3, $D_1$ must be either the same as $D_3$ or $D_4$. Thus, $e_c$ and $e_{c^{\prime }}$ have a common endpoint. $◀$

Lemma 11 implies that ${\zeta }_c$ and ${\zeta }_{c^{\prime }}$ only cross if $e_c$ and $e_{c^{\prime }}$ share an endpoint. Since the only crossings occur between edges incident on the same vertex, $G_D$ can be redrawn with these crossings removed. This immediately implies the following:

We first quickly argue that there is $O(n)$ cells of depth at most 2. By the definition of cell, there is at most $n$ cells of depth 1, one for each ball in $ℛ$. By the existence of a planar dual support (Theorem 2) on $ℛ$ with respect to all vertices of $G$, we know that for every cell of depth 2 corresponding to vertices $v$ incident on balls $R$ and $R^{\prime }$, the connectivity of ${ℛ}_v$ requires that $R$ and $R^{\prime }$ share an edge. Since the dual support is planar, there is at most $3|ℛ|-6$ such pairs, and thus at most $O(n)$ cells of depth 2.

For depth-3 cells, every edge of $G_D$ corresponds to a resident depth-3 cell $c$ of $D$, so $|\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)|\le |E(G_D)|$. By Lemma 12, $|\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)|\le 3|V(G_D)|$. By charging the depth-3 cells to the total number of edges across all $G_D$ for all $D\in ℛ$ using the planarity of $G_D$, $|\mathrm{𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡}(D)|\le 3|N_H(D)|$. Summing over all neighborhoods in the contracted Voronoi diagram of $ℛ$ in $G$, we know the sum of degrees is at most $6|ℛ|$. Thus, $|{\mathrm{𝐶𝑒𝑙𝑙}}_3|\le 18|ℛ|$. $◀$