Approximating Densest Subgraph in Geometric Intersection Graphs

We show a reduction from (shallow) range-reporting to approximate counting/sampling: given a set of objects $𝒟$, and a reporting data-structure for $𝒟$, we show a reduction to building a data-structure, such that given a query object $𝗊$, it returns approximately-at-uniform an object from $𝗊\sqcap 𝒟=\left\{x\in 𝒟\right|x\cap 𝗊\ne \mathrm{\varnothing }\},$ and also returns an $(1\pm \epsilon )$-approximation for the size of this set. Previous work on closely related problem includes the work by Afshani and Chan [1] (that uses shallow counting queries), the work by Afshani et al. [2], and the work by Afshani and Philips [3]. For our application, this data-structure enables us to sample $(1\pm \epsilon )$-uniformly a disk from the set of disks intersecting a given disk. See Section 3 and Theorem 12 for details.

The reduction seems to be new, and should be useful for other problems. For example, in databases, motivated by summarizing large query output size, and to incorporate fairness and diversity in the output results, independent query sampling (IQS) has received quite a bit of attention. In IQS the goal is to report a uniform sample of the query output (i.e., of $𝗊\sqcap 𝒟$). Crucially, the query output should be independent of all the previous queries posed (for example, if the same query is posed again, then the sample reported should be independent of the previous sample). See the survey by Tao [27] on IQS (and the references within). Our reduction addresses two of the future directions proposed in the survey: (a) designing a generic IQS data structure which works for a broad class of geometric queries, and (b) approximate IQS where the probability of reporting an object is almost-uniform, which is usually good enough in practice.

For the sake of concreteness, we consider the case of $n$ disks (with arbitrary radii) lying in the plane and present two different approximation algorithms. See Figure 1.1. However, our algorithms would work for other shapes with minor modifications.

Our first approximation algorithm uses the greedy strategy of removing disks of low-degree from the intersection graph. By batching the queries, and using the above data-structure, we get a $(2+\epsilon )$-approximation for the densest subset of disks in time $O_{\epsilon }(n\log n)$, where $O_{\epsilon }$ hides constants polynomial in $1/\epsilon$. Getting this running time requires some additional ideas such as establishing densest subgraph’s connection with deepest point in the arrangement of disks (defined later). The running time is optimal in terms of $n$ in the comparison-based model, see Remark 20.

A more promising approach is to randomly sample edges from the intersection graph, and then apply known approximation algorithms. This requires some additional work since unlike previous work, we can only sample approximately in uniform. See Section 5 for details. The running time of the new algorithm is $O_{\epsilon }(n{\log }^{2}n\log \log n)$ which is slower than the first $(2+\epsilon )$-approximation algorithm. The results are summarized in Figure 1.2.

Observe that

As such, if , then

But this implies that $𝒪-u$ is denser than $𝒪$, which is a contradiction. $◀$

We break the boundary of each disk at its two $x$-extreme points, resulting in a set of $2n$ $x$-monotone curves. Computing the vertical decomposition of the arrangement of these disks (curves) $𝒜\left(𝒟\right)$ can be done in $O(n\log n+k)$ expected time [20]. See Figure 2.1 for an example. This gives us readily all the pairs that their boundaries intersect.

As for the intersections that rise out of containment, perform a traversal of the dual graph of the vertical decomposition (i.e., each vertical trapezoid is a vertex, and two trapezoids are adjacent if they share a boundary edge). The dual graph is planar with $O(n+k)$ vertices and edges, and as such the graph can be traversed in $O(n+k)$ time. During the traversal, by appropriate bookkeeping, it is straightforward to maintain the list of disks containing the current trapezoid, in $O(1)$ per edge traversed, as any edge traversed changes this set by at most one.

For a disk $𝖽$, let $p_{𝖽}$ be the rightmost point of $𝖽$. For each disk $𝖽$, pick any trapezoid $\mathrm{\Delta }$ such that $p_{𝖽}\in \mathrm{\Delta }$ and either the top boundary of $𝖽$ is the ceiling of $\mathrm{\Delta }$ or the bottom boundary of $𝖽$ is the floor of $\mathrm{\Delta }$. Assign ${\mathrm{\Delta }}_{𝖽}\leftarrow \mathrm{\Delta }$ as the representative trapezoid of $𝖽$.

During the traversal of the dual graph, consider the case where we arrive at a representative trapezoid of a disk $𝖽$. Let $L(𝖽)$ be the list of disks containing ${\mathrm{\Delta }}_{𝖽}$. Then scan $L(𝖽)$ to report all the containing pairs of $𝖽$. Each disk in $L(𝖽)$ either intersects the boundary of $𝖽$, or contain it. Therefore, the total time spent at the representative trapezoids is ${\sum }_{𝖽\in 𝒟}\left|L(d)\right|=O(k)$. $◀$

Let $𝒟$ be a set of $n$ objects, and assume for any subset $X\subseteq 𝒟$ of size $m$, one can construct, in $C(m)$ time, a data-structure that given a query object $𝖽$, returns, in $O(Q(m)+k)$ time, all the objects in $X$ that intersects $𝖽$, where $k=\left|𝖽\sqcap X\right|$. Furthermore, we assume that if a parameter $k^{\prime }$ is specified by the query, then the data-structure stops after $O(Q(m)+k^{\prime })$ time, if $k>k^{\prime }$, and indicate that this is the case.

We build a random binary tree over the objects of $𝒟$, by assigning each object of $𝒟$ with equal probability either a $0$ or a $1$ label. This partitions $𝒟$ into two sets ${𝒟}_0$ (label $0$) and ${𝒟}_1$ (label $1$). Recursively build random trees $T_0$ and $T_1$ for ${𝒟}_0$ and ${𝒟}_1$, respectively, with the output tree having $T_0$ and $T_1$ as the two children of the root. The constructions bottoms out when the set of objects is of size one. Let $𝒯$ be the resulting tree that has exactly $n$ leaves. For every node $u$ of $𝒯$, we construct the reporting data-structure for the set of objects $𝒟(u)$ – that is, the set of objects stored in the subtree of $u$.

Finally, create an array $L_i$ for each level $i$ of the tree $𝒯$, containing pointers to all the nodes in this level of the tree.

Given a query object $𝗊$, and a parameter $\epsilon \in (0,1/2)$, the algorithm starts from an arbitrary leaf $v$ of $𝒯$. The leaf $v$ has a unique root to $v$ path, denoted by $\pi =u_0{u}_1\mathrm{\dots }{u}_t$, where $u_0=\mathrm{root}(𝒯)$ and $u_t=v$. The algorithm performs a binary search on $\pi$, using the reporting data-structure associated with each node, to find the maximal $i$, such that $\left|𝗊\sqcap 𝒟(u_i)\right|>\psi =c\log n$, where $c$ is a sufficiently large constant. Here, we use the property that one can abort the reporting query if the number of reported objects exceeds $\psi$. This implies that each query takes $Q(n)+O(\log n)$ time (with no dependency on $\epsilon$). Next, the algorithm computes the maximal $j$ such that $\left|𝗊\sqcap 𝒟(u_j)\right|>{\psi }_{\epsilon }=c{\epsilon }^{-2}\log n$ (or set $j=0$ if such a $j$ does not exist). This is done by going up the path $\pi$ from $u_i$, trying $u_{i-1},u_{i-2},\mathrm{\dots },u_j$ using the reporting data-structure till the condition is fulfilled²²2One can also “jump” to level $i+{\log }_2(1/{\epsilon }^2)-2$, and do a local search there for $j$, but this “improvement” does not effect the performance.. Next, the algorithm chooses a vertex $u\in L_j$ uniformly at random. It computes the set $S=𝗊\sqcap 𝒟(u)$ using the reporting data-structure. The algorithm then returns a random object from $S$ uniformly at random, and the number $2^j\left|S\right|$. The first is a random element chosen from $𝗊\sqcap 𝒟$, and the second quantity returned is an estimate for $\left|𝗊\sqcap 𝒟\right|$.

Lemma 6 readily implies that $\mathrm{d}\ge (\mathrm{h}-1)/2$, as this is the density provided by the disks containing the deepest point.

As for the other direction, consider the densest subset $𝒪\subseteq 𝒟$, and let $𝖽$ be the smallest disk in $S$. By Lemma 6, the set $T=𝖽\sqcap (𝒪-𝖽)$ has size least $\mathrm{d}$. Let $c$ be the center of $𝖽$ and inscribe an equilateral triangle in $𝖽$. Consider a tiling of $6$ such triangles that are interior disjoint, all sharing a vertex at $c$. Let $P$ be the set of $7$ vertices used by these triangles (including $c$), see Figure 4.1. One can verify³³3Indeed, if the center $c^{\prime }$ of ${𝖽}^{\prime }$ is in the union of the seven copies of $𝖽$ centered at the points of $P$, see Figure 4.1, then the disk ${𝖽}^{\prime }$ must contain one of the points of $P$. Otherwise, it can be verified that $𝖽$ and ${𝖽}^{\prime }$ do not intersect. that any disk ${𝖽}^{\prime }$ at least as large as $𝖽$ that intersect $𝖽$, must contain at least one point of $P$.

Thus, each disk in $T$ is stabbed by at least one point in $P$, which readily implies that there is a point in $P$ that has depth $\left|T\right|/\left|P\right|\ge \mathrm{d}/7$.

As for the last part, a $1.1$-approximation of the deepest point in the arrangement of the disks can be computed in $O(n\log n)$ time [5]. The returned approximate deepest point provides the desired approximation. $◀$

Consider the iteration when $\beta \in [{(1-\vartheta )}^3\mathrm{d},{(1-\vartheta )}^2\mathrm{d}]$. By definition of , all the objects in it have a degree at most $(1+\vartheta )\beta \le (1+\vartheta ){(1-\vartheta )}^2\mathrm{d}\le (1-\vartheta )\mathrm{d}$. By Lemma 6, all the objects in the optimal solution have degree $\ge \mathrm{d}$ (when restricted to the optimal solution). Therefore, none of the objects in the optimal solution are in and hence, the set ${ℒ}_{\ge }$ is not empty (and contains the optimal solution). Inside this round, the loop is performed at most $O({\vartheta }^{-1}\log n)$ times, as every iteration of the loop shrinks $ℒ$ by a factor of $1-\vartheta$. This implies that the algorithm must stop in this round. $◀$

Consider the set $ℒ$, the value of $\beta$ when the algorithm terminated, and let $\nu =\left|ℒ\right|$. By Lemma 16, $\beta \ge {(1-\vartheta )}^3\mathrm{d}$, and by the algorithm stopping condition, we have In addition, all the objects in ${ℒ}_{\ge }$ have degree at least $(1-\vartheta )\beta$. Thus, the number of induced edges on $ℒ$ is

Thus $\nabla \left(ℒ\right)=\frac{𝗆\left(ℒ\right)}{\left|ℒ\right|}\ge (1-5\vartheta )\mathrm{d}/2=(1-\epsilon /3)\mathrm{d}/2$, as $\vartheta =\epsilon /15$. Observe that $2/(1-\epsilon /3)\le 2(1+\epsilon /2)\le 2+\epsilon$. $◀$

The expected time spent, in an iteration, in step I and II is $O({\vartheta }^{-2}n\log n)$, where $n=\left|ℒ\right|$, and this dominates the running time of this iteration. Let $n_i$ be the size of $ℒ$ in the $i$th iteration (inside the same round), and observe that $n_{i+1}\le (1-\vartheta )n_i$. Assume $t$ iterations are performed inside this round. As ${\sum }_{i=1}^t{n}_i=O(n/\vartheta )$, the expected running time for the round is ${\sum }_{i=1}^{t}O({\vartheta }^{-2}{n}_i\log n_i)=O({\vartheta }^{-3}n\log n)$. The value of $\beta$ can change $O(1/\epsilon )$ times during the algorithm and hence, the overall expected running time of the algorithm is $O(n{\vartheta }^{-4}{\log }^{2}n)$, which implies the result since $\vartheta =\mathrm{\Theta }(\epsilon )$. $◀$

Summarizing, we get the following.