The Maximum Clique Problem in a Disk Graph Made Easy

A geometric intersection graph consists of a set of geometric objects as vertices and a set of edges that are determined by the intersection of these objects, i.e., two vertices are considered adjacent if and only if the corresponding objects intersect. Geometric objects of different shapes and their intersection graphs are often used to model applied contexts, e.g., unit disks for problems in wireless networks [24, 28], line segments (time intervals) for task scheduling [34], trapezoids for channel routing in VLSI design [23], etc. Many NP-hard graph problems are known to admit polynomial-time solutions on various types of geometric intersection graphs (see e.g., [8, 16]). There also exist cases where a graph problem is known to be NP-hard, but its time complexity status is open for some intersection graph class (see e.g. the open problems posed in [2, 1, 5, 33]). In this paper, we restrict our attention to one such scenario, where the problem of interest is finding a maximum clique, i.e., a maximum subset of pairwise adjacent vertices, and the intersection graph we examine is a disk graph. Here, a disk graph $G$ is an intersection graph of disks in ${ℝ}^2$, where each vertex of $G$ corresponds to a disk and two vertices are adjacent in $G$ if and only if their disks intersect.

The maximum clique problem is NP-hard for many well-known intersection graph classes such as intersection graph of rays [13], grounded strings [33], triangles [3], ellipses [3], and a combination of axis-aligned rectangles and unit disks [7, 21], whereas polynomial-time solvable for circle graphs [36], trapezoid graphs [23], circle trapezoid graphs [23], unit disk graphs [16], axis-aligned rectangle intersection graphs [29], and so on. However, determining the time complexity of computing a maximum clique in a disk graph is a long-standing open question [3, 4, 24]. In a seminal paper published in 1990, Clark, Colbourn, and Johnson [16] gave a polynomial-time algorithm for the case of unit disk graphs. However, the time-complexity question for general disk graphs has remained open since then. Although this was not posed as an open problem in [16], it has long been known to be a challenging problem [4], even before it was explicitly posed as an open problem (e.g., by Fishkin [24], Ambühl and Wagner [3] and Cabello [11, 12]). In fact, the problem has been emphasized in various ways in the literature, e.g., as “an intriguing open question”, as “a notorious open question in computational geometry” [5], as being “elusive with no new positive or negative results” [4], and several times as a “long-standing open problem” [21, 25, 27].

Although no polynomial-time exact solution is known for finding a maximum clique in general disk graphs, a 2-approximate solution [3] can be obtained by guessing all stabbing sets of four points. There always exists a stabbing set of at most four points for every set of disks that forms a clique [17, 39, 14]. Therefore, one can take the largest solution obtained from all guesses. However, obtaining a better approximation ratio appears to be a challenge. Cabello [11, 12] even asked whether a 1.99 approximation can be achieved if we restrict the input to disks that have at most two different sizes of radii.

Several recent research has shown interesting progress on various fronts of the problem. The $O(n^{4.5})$-time algorithm for finding a maximum clique in a unit disk graph [16], which was improved first to $O(n^{3.5}\log n)$-time [9] and then to $O(n^3\log n)$-time [19], has been improved further in SoCG’23 to $O(n^{2.5}\log n)$ [21]. Chan [15] observed that the running time of [21] can be expressed as $O(n\cdot h{(m)}^{1+o(1)})$, where $h(m)$ is the time to compute a maximum matching in a bipartite graph that has a biclique cover²²2A biclique cover of a bipartite graph $G$ is a set of complete bipartite subgraphs of $G$ that cover the edges of $G$. The size of the cover is the number of elements in the set. of size $m$, and $m$ in this context is known to be $O(n^{4/3}\mathrm{polylog}(n))$ [31]. One can leverage such a biclique cover to compute a maximum matching in $O(m^{1+o(1)})$ time [22]. Therefore, the overall running time becomes $O(n^{7/3+o(1)})$. In FOCS’18, the authors in [6] gave a QPTAS, a randomized EPTAS (and thus a fixed-parameter-tractable algorithm [7]), and a subexponential algorithm for computing a maximum clique in a disk graph. They also showed how to extend these results for unit ball graphs, which are intersection graphs of 3-dimensional balls of unit radius. In SODA’22, the authors in [35] designed further subexponential-time fixed-parameter-tractable algorithms for many other fundamental graph problems on disk graphs. While the maximum clique problem is open for disk graphs with arbitrary radii, it is NP-hard for ball graphs [6]. The hardness result holds in a very restricted setting with all radii falling within the interval $[1,1+ϵ]$, $ϵ>0$, where even a subexponential-time approximation scheme is unlikely unless the exponential-time-hypothesis [30] fails.

A rich body of research examined the maximum clique problem in the intersection graph of various types of convex shapes. A $t$-directional convex polygon is a polygon with sides parallel to one of the prespecified $t$ directions. A $t$-directional convex graph is an intersection graph of $t$-directional polygons. The paper in [10] showed that a maximum clique in $k$-directional convex graphs can be solved in time $O(n^{k+3})$ time, and given a geometric representation, this can be improved to $O(n^{k+1})$. The maximum-clique problem can be solved in polynomial time for the intersection graph of unit disks and 2-pancakes [26], where a 2-pancake is defined using a segment on the x-axis. Specifically, a 2-pancake is the Minkowski sum of the unit disk centered at $(0,0)$ and the line segment with endpoints $(x_1,0)$ and $(x_2,0)$, i.e., the union of all unit disks with center on the line segment $x_1{x}_2$. Bonnet, Grelier, and Miltzow [7] extends the polynomial-time algorithm for unit disks [16] to translates of any fixed convex set. This algorithm does not generalize any further, i.e., no polynomial-time algorithm is known for the translates of two fixed convex sets.

In this section we discuss some notation and preliminary results.

By $D_{a,r}$, we denote a disk with a center at point $a$ and radius $r$. Given a pair of disks $D_{a,r}$ and $D_{b,r^{\prime }}$, we refer to their common intersection region as a lens (Figure 1(a)). Let $G$ be a disk graph. For simplicity, sometimes we say a pair of disks are adjacent in $G$, which means that the disks intersect and their corresponding vertices are adjacent in $G$. By $B_{a,r}$, we denote a ball with a center at point $a$ and radius $r$.

For a pair of points $a$ and $b$, we denote the line passing through them as ${\mathrm{\ell }}_{ab}$. By $ab$ and $|ab|$ we denote the line segment with endpoints $a,b$ and the Euclidean distance between $a$ and $b$, respectively. By ${\mathrm{\ell }}_p^h$ and ${\mathrm{\ell }}_p^v$ we denote the horizontal and vertical lines through a point $p$, respectively. By an upper slab $U_{ab}$ of $ab$, we denote the region above $ab$, which is bounded by the lines ${\mathrm{\ell }}_a^v$ and ${\mathrm{\ell }}_b^v$. Similarly, by a lower slab ${\overline{U}}_{ab}$ we denote the region below $ab$, which is bounded by ${\mathrm{\ell }}_a^v$ and ${\mathrm{\ell }}_b^v$.

In this section we give an ${𝒪}^{\ast }(n^{2k})$-time algorithm to find a maximum clique in a disk graph where $k$ is the number of different types of radii.

We first introduce some notation. Let ${𝒟}_k$ be a disk graph where the number of different types of radii is at most $k$. For convenience, we denote these different types of radii as $r_1,r_2,\mathrm{\dots },r_k$, where for every , we have . By a type-$i$ disk we denote a disk of radius $r_i$. Let $𝒞$ be a maximum clique of ${𝒟}_k$. By ${𝒞}_i$ we denote a maximal clique in $𝒞$ where all disks are of type $i$.

The idea of the algorithm is as follows. We guess the number of different types of radii that may appear in a maximum clique and we take the maximum over all the solutions computed from these $2^k$ guesses. We now describe how a solution is computed for a particular guess for a set of radii that may appear in the maximum clique $𝒞$. For each disk type $i$, we guess two disk centers $a_i,b_i$ from ${𝒞}_i$, where $a_i$ is the leftmost (i.e., with the smallest $x$-coordinate) and $b_i$ is the rightmost (i.e., with the largest $x$-coordinate) over all the disk centers in ${𝒞}_i$. Note that $a_i$ may coincide with $b_i$ if ${𝒞}_i$ contains only one disk, or if the centers of all disks in ${𝒞}_i$ are on a vertical line. Let $\mathrm{\Psi }$ be the set of these $2k$ disks. For every upper slab $U_{a_i{b}_i}$, we construct a set $X_i$ by taking every disk that has its center in $U_{a_i{b}_i}$ and intersects all the disks of $\mathrm{\Psi }$. We show that the union of these disks, i.e., $X=(X_1\cup X_2\cup \mathrm{\dots }\cup X_k)$, is a clique in ${𝒟}_k$. Similarly, for each lower slab ${\overline{U}}_{a_i{b}_i}$, we construct a set $Y_i$ by taking every disk that has its center in ${\overline{U}}_{a_i{b}_i}$ and intersects all the disks of $\mathrm{\Psi }$. We show that their union $Y=(Y_1\cup Y_2\cup \mathrm{\dots }\cup Y_k)$ is a clique in ${𝒟}_k$. Since the disks of $\mathrm{\Psi }$ are assumed to be in $𝒞$, it is straightforward to observe that $𝒞$ is a subset of the disks in $(\mathrm{\Psi }\cup X\cup Y)$. Since the complement of the disk graph determined by the disks $(X\cup Y)$ is a bipartite graph $H$, we can compute the maximum clique $𝒞$ from a maximum bipartite matching in $H$. It now suffices to show that the disks in $X$ (similarly, the disks in $Y$) are mutually adjacent.

In this section, we consider the problem of reporting a maximum clique given a rectangular range query over an arrangement of unit disks. To this end, we show how to compute a maximum clique for every axis-aligned rectangle (determined by the input disk centers) in $O(n^5\log n)$ time, which is at least a factor of $n^{4/3}$ faster than applying the algorithm of [21] separately for each axis-aligned rectangle.

To better explain such advantages of our technique, we first give an overview of the existing algorithms to compute a maximum clique in a unit disk graph. The idea of Clark, Colbourn, and Johnson’s $O(n^{4.5})$-time algorithm [16] is to guess the farthest pair of vertices $(v,w)$ in the clique, and then to find a maximum clique $C$ that contains both $v$ and $w$. Since $v$ and $w$ are the farthest pair, the set $S$ of vertices that are adjacent to both $v,w$ must lie in a lens-shaped region, i.e., the common intersection region of the two disks centered at $v$ and $w$ with radius $|vw|$. They showed that the lens can be partitioned by the line segment $vw$ into two halves where the disks with centers in the same half are pairwise intersecting. Consequently, the complement of the disk graph corresponding to $S$ is a bipartite graph $H$, and the maximum clique $C$ can be computed by finding a maximum independent set in $H$. The running time for the unit disk case has subsequently been improved to $O(n^{3.5}\log n)$ by using non-trivial data structures [9], then to $O(n^3\log n)$ by examining the lenses in a particular order so that the solution for each lens does not need to be computed from scratch [19, 20], and finally, to $O(n\cdot h{(m)}^{1+o(1)})$ by a combination of divide-and-conquer and plane sweep approach using a circular arc [21, 15]. Here $h(m)$ is the time to compute a maximum matching in $H$, i.e., the complement of the disk graph inside a lens, and $m$ is the size of the biclique cover of $H$. Since $m\in O(n^{4/3}\mathrm{polylog}(n))$ [31] and a maximum matching can be computed using a maximum-flow algorithm in $O(m^{1+o(1)})$ time [22], the running time becomes $O(n^{7/3+o(1)})$. Consider now the scenario of computing a maximum clique for every possible rectangle determined by the input disk centers. Since lenses examined by these algorithms are not necessarily axis-aligned, finding an order of the lenses to compute solutions for the rectangles by dynamic point insertion and deletion appears to be challenging. A straightforward approach that solves each rectangular region independently takes $O(n^{6.33+o(1)})$ time.

The idea of our algorithm is to maintain solutions for all possible slabs where one can insert and delete points as necessary to find the solutions for all possible rectangles within the slab. For convenience, we assume that the centers of the disks are in general position, i.e., no two centers have the same $y$-coordinates. We now describe the details.

Consider first an alternative (slower) approach that uses slabs to compute a maximum clique that guesses the leftmost and rightmost points $a,b$ of a maximum clique. For every such guess, one can find a maximum clique by considering the set $S$ of disks that are adjacent to both $a,b$ and have their centers in the slab bounded by ${\mathrm{\ell }}_a^v$ and ${\mathrm{\ell }}_b^v$. By Lemma 1, the disks of $S$ that have their centers in $U_{ab}$ (similarly, in ${\overline{U}}_{a,b}$) are mutually adjacent. Consequently, the complement of the disk graph underlying $S$ is a bipartite graph $H$, and a maximum clique can be computed by finding a maximum independent set in $H$.

We now consider maintaining the solutions for all possible slabs under point insertion and deletion. Initially, the solution for each slab is set to null. We now sweep the plane upward with two horizontal lines ${\mathrm{\ell }}^b$ and ${\mathrm{\ell }}^u$ in two phases.

In the first phase, ${\mathrm{\ell }}^b$ is placed so that it passes through the disk center with the lowest $y$-coordinate, and ${\mathrm{\ell }}^u$ is used to sweep the plane upward starting at ${\mathrm{\ell }}_b$. Each time ${\mathrm{\ell }}^u$ moves to a new point, a point is inserted into the corresponding slabs and their solutions are updated. Every time the horizontal slab between ${\mathrm{\ell }}^b$ and ${\mathrm{\ell }}^u$ contains the guessed points of a slab (i.e., the two points determining a slab), we obtain a solution for a new rectangular region, and the corresponding solution is stored in a table. It is straightforward to observe that each insertion changes $O(n^2)$ slabs, and hence we have $O(n^3)$ insertion operations in total.

In the next phase, we sweep the plane upward using ${\mathrm{\ell }}^b$. Each time ${\mathrm{\ell }}^b$ moves to a new point, a point is deleted from the corresponding rectangular regions we considered in the first phase. A deletion changes $O(n^3)$ previous solutions, i.e., the solutions corresponding to $O(n^2)$ slabs and $O(n)$ regions in each slab determined by the positions of ${\mathrm{\ell }}_b$. Therefore, we have $O(n^4)$ deletion operations in total.

Each insertion and deletion operation updates existing lenses, each of which is determined by a pair of guessed points. It is known that such updates can be done in $O(n\log n)$ time by performing an alternating path search to update the maximum independent set in the bipartite graph determined by the complement of the disk graph inside the lens [20, 19]. For $O(n^4)$ update operations, the running time becomes $O(n^5\log n)$. By $S[p_{\mathrm{\ell }},p_r,p_t,p_b]$ we denote the size of a maximum clique inside a rectangle $R$ with its left, right, top and bottom sides being determined by the lines through the disk centers $p_{\mathrm{\ell }},p_r,p_t,p_b$, respectively, where $|p_{\mathrm{\ell }},p_r|$ is at most two units and $p_{\mathrm{\ell }},p_r$ appear on the left and right sides of $R$. If $|p_{\mathrm{\ell }},p_r|$ is larger than two units, then $S[p_{\mathrm{\ell }},p_r,p_t,p_b]$ is 0.

We now compute a maximum clique for each axis-aligned rectangle determined by the input disk centers. We first compute two sorted orders of the disk centers, one based on increasing $x$-coordinates and the other based on increasing $y$-coordinates. We now use a dynamic programming approach, where the base cases are the entries of $S$, and the $O(n^4)$ rectangles that do not contain any disk center in their proper interior. The latter can be computed and stored in a table in $O(n^4)$ time. Let $M[p_{\mathrm{\ell }},p_r,p_t,p_b]$ be the maximum clique of a rectangle $R$ with its left, right, top and bottom sides being determined by the lines through $p_{\mathrm{\ell }},p_r,p_t,p_b$, respectively. Note that the disk centers of the maximum clique may not appear on the sides of $R$. Let $p_{\mathrm{\ell }}^{\prime }$ and $p_r^{\prime }$ be the disk centers immediately after and before $p_{\mathrm{\ell }}$ and $p_r$, respectively, which can be determined from the precomputed sorted order. Similarly, $p_t^{\prime }$ and $p_b^{\prime }$ are the disk centers immediately before and after $p_t$ and $p_b$, respectively. We now can find a solution using $O(1)$ table look-ups as follows.

Since there are $O(n^4)$ cells in the table and each entry is computed by $O(1)$ table look-ups which are determined in $O(\log n)$ time, the overall running time remains $O(n^5\log n)$.

We now give an ${𝒪}^{\ast }(n^{2rk})$-time algorithm for computing a maximum clique in a ball graph, where the centers of the balls are contained in $r$ planes which are all perpendicular to a different plane (Section 5.2). For simplicity, we first consider a scenario when the input planes are parallel to each other (Section 5.1).

In this section we give an ${𝒪}^{\ast }(n^{2k})$-time algorithm to compute a maximum clique in the intersection graph of $n$ $L$-visible convex polygons with $k$ distinct shapes. Figure 3(a) illustrates an $L$-visible polygon, where every point of the polygon is $L$-visible from a center point $c$.

We first introduce some notation. Let ${𝒮}_k$ be an intersection graph of $L$-visible polygons, where the number of different types of shapes is at most $k$. For convenience, we denote these shapes as $S_1,S_2,\mathrm{\dots },S_k$ and for each shape $S_i$, designate a center $c_i$, i.e., all points of $S_i$ are $L$-visible from $c_i$. Let $𝒞$ be a maximum clique of ${𝒮}_k$. By ${𝒞}_i$ we denote a maximal clique in $𝒞$ where all shapes are of type $i$. We also use the following properties of $L$-visible shapes which are straightforward to verify using the concept of Minkowski sum of two convex polygons [18].

The idea of the algorithm is similar to that of Section 3. We guess the set of different types of shapes that may appear in a maximum clique and we take the maximum over all the solutions computed from these $2^k$ guesses. For each type $i$, we guess the leftmost and rightmost shape centers $a_i$ and $b_i$, respectively, over the shapes in ${𝒞}_i$. Let $\mathrm{\Psi }$ be the set of these $2k$ shapes. For every upper slab $U_{a_i{b}_i}$, we construct a set $X_i$ by taking every shape that has its center in $U_{a_i{b}_i}$ and intersects all the shapes of $\mathrm{\Psi }$. We show that the union of these shapes, i.e., $X=(X_1\cup X_2\cup \mathrm{\dots }\cup X_k)$, is a clique in ${𝒮}_k$. Similarly, for each lower slab ${\overline{U}}_{a_i{b}_i}$, we construct a set $Y_i$ by taking every shape that has its center in ${\overline{U}}_{a_i{b}_i}$ and intersects all the shapes of $\mathrm{\Psi }$. We show that their union $Y=(Y_1\cup Y_2\cup \mathrm{\dots }\cup Y_k)$ is a clique in ${𝒮}_k$. A maximum clique can then be found from a maximum bipartite matching in the complement of the intersection graph of $(X\cup Y)$. The time to compute the graph and the matching is polynomial in $n$ and $m$, where $m$ is the shape complexity, i.e., upper bound on the number of smooth curves on the boundary of a shape.

We gave an ${𝒪}^{\ast }(n^{2k})$-time algorithm to find a maximum clique in a $n$-vertex disk graph with $k$ different radii. Designing faster algorithms is a natural direction to explore. Existing techniques [38] that computes maximum clique on unit disk graphs even when a geometric representation is not given do not generalize to our context. Therefore, finding efficient algorithms when a geometric representation of the disk graph is not given would be interesting.

We showed that given a set of $n$ unit disks, one can compute a maximum clique for each possible axis-aligned rectangle determined by the input disk centers in $O(n^5\log n)$ time. Consequently, given a rectangular range query $R$, the maximum clique $C$ inside $R$ can be reported in $O(\log \log n+|C|)$ time, where the $O(\log \log n)$ term is to locate the rectangle $R^{\prime }$ (using range searching data structures [37]) for which a solution is precomputed. Improving the $O(n^5\log n)$ running time or establishing tight time-space trade-offs can be interesting.

For ball graphs, we gave an ${𝒪}^{\ast }(n^{2rk})$-time algorithm to find a maximum clique, where $k$ is the number of different radii and the ball centers are contained in $r$ planes that are perpendicular to a single different plane. One may attempt to relax our perpendicularity constraint. The NP-hardness reduction for computing a maximum clique in a ball graph [6] allows for arbitrary radii whereas our result provides polynomial-time algorithms when $r,k\in O(1)$. The case when $k\in o(n)$ can be explored. Finally, can we find a polynomial-time algorithm for computing maximum clique in the intersection graph of convex shapes that are not necessarily $L$-visible, where the number of distinct shapes is fixed?