This post is about my recent preprint with Hsien-Chih Chang and Jie Gao, on the problem of computing diameter of unit disk graphs. (I have not written about my recent papers, and I think I should write more, especially about things that are not included in the papers.)
A unit disk graph with \(n\) vertices is the intersection graph of \(n\) disks on the plane: two vertices have an edge if their two corresponding disks intersect. Here is an example of a unit disk graph; the figure is by David Eppstein on wikipedia:
A unit disk graph could have \(\Omega(n^2)\) edges and hence we often work with its disk representation that only has \(O(n)\) space, hoping to also design algorithms with \(O(n\mathrm{polylog}(n))\) time. For example, single-source shortest path in unit disk graphs can be solved in \(O(n\log n)\) time. Could we design an algorithm for computing diameter with the same running time? This problem currently seems out of reach. An easier problem is to compute the diameter of unit disk graphs in truly subquadratic time. This turns out to be a long-standing open problem.
Open Problem: Can the diameter of \(n\)-vertex unit disk graphs be computed in \(O(n^{2-\epsilon})\) time for any constant \(\epsilon > 0\)?
Our recent paper does not resolve this problem, but makes non-trivial progress. We showed that:
- Computing diameter within an additive error of \(+2\) can be done in truly subquadratic time, specifically, \(\tilde{O}(n^{2-1/18})\) time. That is, if the true diameter is \(d\), then our algorithm outputs a number between \(d\) and \(d+2\).
- If the ply of the set of disks is relatively small, \(O(n^{1/22-\epsilon})\) for a fixed \(\epsilon > 0\), then we can compute diameter exactly in truly subquadratic time.
We also obtained several related results, such as computing the diameter of similar-size pseudo-disk graphs and approximate distance oracles; do check out the paper for details.
Note that there were several negative results. The analog of unit disk graphs in higher dimensions is unit ball graphs. However, in dimension 3 or above, computing diameter cannot be computed in truly subquadratic time, assuming the Orthogonal Vector (OV) conjecture by this paper. They also showed that the intersection graphs in dimension 2 of several other types of objects, such as congruent equilateral triangles or axis-parallel line segments, do not have truly subqudratic time algorithm for diamter, assuming OV conjecture. So, something is very special about unit disk graphs.
A New Technique: VC Dimension
A key new idea in our paper is VC dimension. VC dimension has been used to compute diameter of planar graphs, and minor-free graphs, including my own work in SODA24 along this line. There are several different ways to define VC set systems, but two of them are of special interest here.
Distance VC dimension: The ground set is the vertex set \(V\) of the graph, and the family of subsets \(\mathcal B\) are balls.
\[\mathcal B = \{B_r(v): v\in V, r\in \mathbb{R}^+\}\]
Here \(B_r(v) = {u: d_G(u,v)\leq r}\) is the ball of radius \(r\) centered at \(v\). We show that:
Theorem 1: If \(G\) is an intersection graphs of pseudo-disks, then \((V, \mathcal B)\) has VC dimension at most 4.
Our result holds for intersection graphs of pseudo-disks of any size, which vastly generalize unit-disk graphs. The proof uses a topological argument. And this proof is the most intersecting part of the paper in my opinion.
An independent result by Duraj, Konieczny, and Potępa showed the same VC dimension bound for a special case of unit disk graphs, and, in general, geometric intersection graphs of objects that are closed, bounded, convex, and center symmetric. Their proof is different and based on geometry.
Distance encoding VC dimension: The defintion is somewhat hard to parse.
Definition: Let \(M\subseteq \mathbb{R}\) be a set of real numbers. Let \(S={s_0, s_1, \ldots, s_{k-1}}\) be a sequence of \(k\) vertices in an undirected weighted graph \(G=(V, E)\). For every vertex \(v\) define
\[X(v) = \{ (i, \Delta) : 1\leq i \leq k-1, \Delta \in M, d(v, s_i)-d(v, s_0)\leq \Delta \}.\]
\(\mathcal{LP} = {X(v) : v\in V}\) be a set of subsets of the ground set \([k-1]\times M\).
It’s a mouthful. Intuitively, the set \(X(v)\) captures the distance from \(v\) to vertices in \(S\) compared to the distance to \(s_0\). One can think of \(X(v)\) as encoding the distance vector from \(v\) to vertices in \(S\): each pair \((i, \Delta)\) tells us the (approximate) distance from \(v\) to \(s_i\) relative to the distance from \(v\) to \(s_0\). A variant of this set system was introduced for planar graphs in a beautiful paper of Li and Parter. The one defined above is a slight modification of the set system of Li and Parter, which appeared in my paper with Christian. This paper showed that the set system has bounded VC dimension in minor-free graphs. Here, we show that the VC dimension remains bounded in pseudo-disk graphs. The proof is almost the same as the proof of Theorem 1.
Theorem 2: If \(G\) is an intersection graphs of pseudo-disks, then \(([k-1]\times M, \mathcal{LP})\) has VC dimension at most 4.
VC Dimension and Computing Diameter
There are two different techniques for computing diameter using VC dimension. The first technique constructed a spanning path with a low stabbing number using the distance VC dimension (the system of balls). This technique was introduced by Ducoffe, Habib, and Viennot to compute the diameter of graphs with sublinear separators. The second technique combines the distance encoding VC dimension and \(r\)-division. This technique was used to compute the diameter of minor-free graphs.
Here, we follow the second technique, using the distance encoding VC dimension. Since unit disk graphs do not have \(r\)-division, we develop an analogous version called clique-based \(r\)-clustering. The error +2 is due to the clique-based \(r\)-clustering step. If one somehow eliminates the clique-based \(r\)-clustering, then one solves the open problem mentioned above.