Computing the Girth of a Segment Intersection Graph

The previous separator-based approach faces an $n^{3/2}$ barrier because min-plus matrix multiplication is widely conjectured to require near-cubic time (according to the “All-Pairs Shortest Paths (APSP) hypothesis” from fine-grained complexity [45]). Our first idea is to employ recent results which solve certain powerful special cases of min-plus product in truly subcubic time – namely, the case when the input matrices are integer-valued and satisfy a bounded-difference property, i.e., the difference between any two adjacent entries (in each row or in each column) is at most a constant. Chan and Lewenstein [16] gave the first truly subquadratic algorithm for the related min-plus convolution problem for bounded-difference sequences, while Bringmann et al. [9] gave the first truly subcubic algorithm for bounded-difference min-plus product. Bringmann et al.’s original algorithm ran in $O(n^{2.8244})$ time, and after a series of improvements [31, 20], Chi et al. [21] obtained the current best running time of $\tilde{O}(n^{(3+\omega )/2})\le O(n^{2.686})$ (see Section 2.1).

Bounded-difference min-plus convolution and matrix multiplication have recently been applied to solve a variety of problems from different domains, including language edit distance and RNA folding [9], single-source replacement paths and Range Mode [31], tree edit distance [40], approximate APSP [43], knapsack [7, 8], etc. Our algorithm, being one of the first applications to a computational geometry problem, is thus noteworthy.

Why is the bounded-difference property relevant in our application? Suppose the separator $S$ is connected, e.g., is a cycle (as in Miller’s version of the separator theorem [41]). Then for any vertex $q$ and two adjacent separator vertices $s,s^{\prime }\in S$, $d(s,q)$ and $d(s^{\prime },q)$ differ by at most 1 due to the triangle inequality. Thus, the distance matrices we encounter during recursion would indeed satisfy the bounded-difference property.

Unfortunately, cycle separators do not always exist when the given planar graph is not $2$-connected. Our key idea is to use an interesting variant of the planar-graph separator theorem, which holds for any planar graphs: given any $\alpha >0$, there always exists a separator $S$ consisting of two subsets $P$ and $Q$, where

• $\mathrm{■}$

  the first subset $P$ has size $O(n^{1/2+\alpha })$ but has at most 2 connected components (in fact, at most 2 paths);

• $\mathrm{■}$

  the second subset $Q$ may not be connected but has size $O(n^{1/2-\alpha })$.

We are not aware of this variant of the separator theorem explicitly stated before (though we will not be surprised if it appeared before), but it follows by straightforward modification of standard proofs. See Section 2.2 for the precise statement and proof.

This variant of separators is exactly the tool we need to break the $n^{3/2}$ barrier: since $P$ has only $O(1)$ connected pieces, we can use bounded-difference min-plus products to compute distances involving $P$ faster; on the other hand, since $Q$ has size $\ll \sqrt{n}$, we can afford to compute distances involving $Q$ more naively. We choose the trade-off parameter $\alpha$ carefully to balance cost. This is the main high-level idea of our algorithm. Quite a bit of technical effort, however, is needed to make the idea work (for example, the number of connected components may grow as we recurse, but not by much, as we will show, and we eventually need two separate recursive algorithms, one for computing distances and one for computing the girth). See Sections 3–4 for the detailed algorithm and analysis.

When computing a shortest path between two vertices, we do not need to worry about ensuring simplicity of the path, since a shortest walk must automatically be a shortest path (if a vertex is repeated, we can take a short-cut to obtain a shorter walk). However, more care is needed for the shortest cycle problem in undirected graphs. When concatenating several shortest paths to form a candidate cycle (via min-plus products of several distance matrices), one potential issue is that the resulting closed walk might become trivial (we might be completely retracing our steps, so that short-cutting yields an empty walk!). The earlier algorithm by Chan [14] for detecting constant-length cycles used the color-coding technique [3] to ensure simplicity, but unfortunately color-coding yields exponential dependence on the cycle length. For general graphs, there are other strategies to ensure simplicity, (e.g., by computing shortest paths in different subgraphs with some vertices and edges removed, or with directions added, so as to avoid concatenating two identical shortest paths). But ensuring simplicity is trickier in our setting, since we need to retain the bounded-difference property if we work with new subgraphs. Still, we have found one way to deal with this technical issue, using ideas given in Section 2.3.

We first assume that $G$ is connected. Let $𝒯$ be a BFS tree of $G$ from a fixed source vertex. For any $uv\notin 𝒯$, let $\mathrm{cycle}(𝒯,uv)$ denote the unique cycle in $𝒯\cup \{uv\}$ (called the fundamental cycle), which consists of $uv$ and the unique path in $𝒯$ connecting $u$ and $v$.

Let $\mathrm{\Sigma }$ be a (combinatorial) triangulation of $𝒯$. Define face weights of $\mathrm{\Sigma }$ by examining each vertex $v$, picking an arbitrary incident face $f$, and adding $v$’s weight to $f$. Then the total face weight is $W$. Consider the dual tree with respect to $𝒯$ in $\mathrm{\Sigma }$ (which has maximum degree 3). By standard results on tree separators [34, 28]. we can find an edge which separates this dual tree into two parts each with total face weight at most $3W/4$. In $\mathrm{\Sigma }$, this corresponds to an edge $uv$ such that either side of $C=\mathrm{cycle}(𝒯,uv)$ has total face weight at most $3W/4$; this also bounds the total weight of the vertices strictly inside/outside $C$. If $\left|C\right|\le p$ then the desired separator can obtained by setting $P=C$ and $Q=\mathrm{\varnothing }$. Below we may assume $\left|C\right|>p$.

Let $x$ be the lowest common ancestor of $u,v$ in $𝒯$, and ${𝒯}^{\prime }$ be the subtree of $𝒯$. Let $L_i\subset V$ be the set of vertices in level $i$ of ${𝒯}^{\prime }$ (with $L_0=\mathrm{\varnothing }$). Let $m$ be the smallest integer such that the total weight of vertices in the first $m$ levels of ${𝒯}^{\prime }$ is at least $W/2$. By the pigeonhole principle, there exists $\mathrm{\ell }\in [m-p,m)$ such that $L_{\mathrm{\ell }}$ has total load at most $\mathrm{\Lambda }/p$. Similarly there exists $h\in (m,m+p]$ such that $L_h$ has total load at most $\mathrm{\Lambda }/p$.

If $V_{\le \mathrm{\ell }}={\bigcup }_{i=1}^{\mathrm{\ell }}{L}_i$ has weight at least $W/4$, then since $V_{\le \mathrm{\ell }}$ has weight at most $W/2$ by definition of $m$, the desired separator can be obtained by setting $Q=L_{\mathrm{\ell }}$ and $P=\mathrm{\varnothing }$.

Similarly, if $V_{\ge h}={\bigcup }_{i=h}^{\mathrm{\infty }}{L}_i$ has weight at least $W/4$, then the desired separator can be obtained by setting $Q=L_h$ and $P=\mathrm{\varnothing }$.

In the remaining case, $V_m={\bigcup }_{i=\mathrm{\ell }+1}^{h-1}{L}_i$ has weight at least $W/2$. Let $V_{\mathrm{in}},V_{\mathrm{out}}$ be the set of vertices in $V_m$ that are strictly inside or outside $C$, respectively. Without loss of generality, say $V_{\mathrm{in}}$ has weight at least $W/4$. Recall that $V_{\mathrm{in}}$ has weight at most $3W/4$ by definition of $C$. Let $P_u$ (resp. $P_v$) be the portion of the shortest path from $x$ to $u$ (resp. $v$) with levels between $\mathrm{\ell }$ and $h$. Then $P_u$ and $P_v$ are paths of length $O(p)$. The desired separator can be obtained by setting $P=P_u\cup P_v$ and $Q=L_{\mathrm{\ell }}\cup L_h$. See Figure 2.

Finally, we consider the general case when $G$ may have multiple connected components. If all components have weight at most $W/2$, a trivial separator exists with $S=\mathrm{\varnothing }$. On the other hand, if $G$ has one component of weight at least $W/2$, we can apply the lemma to the largest-weight component and add the remaining components to the smaller of the two subsets $V_1,V_2$ in terms of weight (which would still have total weight at most $3W/4$). $◀$

Suppose that two consecutive edges of $C$ are identical, i.e., we see 3 consecutive vertices $u,v,u$ in $C$. If $uv$ is the last edge of ${\pi }_i^R$ and $vu$ is the first edge of ${\tau }_i$, then $u$ and $v$ are white vertices and we can remove $v$ from $C$ and still have a closed walk satisfying the stated condition. If $uv$ is the last edge of ${\pi }_i^R$, and ${\tau }_i$ is empty, and $vu$ is the first edge of ${\pi }_i^B$, then $u$ and $v$ must again be white vertices and we can remove $v$ from $C$ and still have a closed walk satisfying the stated condition. After handling all other similar cases, we may assume that no two consecutive edges of $C$ are identical. Now, $C$ forms a subgraph where every vertex has degree at least 2, and so must contain a nontrivial simple cycle. $◀$

For (i), consider a shortest legal alternating closed walk $C$. Then $C$ is the concatenation of simple paths ${\pi }_0^R,{\tau }_0,{\pi }_0^B,{\tau }_0^{\prime },\mathrm{\dots },{\pi }_{k-1}^R,{\tau }_{k-1},{\pi }_{k-1}^B,{\tau }_{k-1}^{\prime }$ with $k\ge 1$, where each ${\pi }_i^R$ is a legal red path, each ${\pi }_i^B$ is a legal blue path, and each ${\tau }_i$ and ${\tau }_i^{\prime }$ lie in $G[W]$. Each ${\pi }_i^R$ must pass through at least one red vertex, because ${\delta }_{G[R\cup W]}(u({\pi }_i^R),v({\pi }_i^R))\ne {\delta }_{G[W]}(u({\pi }_i^R),v({\pi }_i^R))$, where $u(\pi )$ and $v(\pi )$ denote the starting and ending vertices of a path $\pi$. Similarly, each ${\pi }_i^B$ must pass through at least one blue vertex. So, the condition in Lemma 3 is satisfied, and $C$ must contain a nontrivial simple cycle. Hence, the girth of $G$ is at most the length of $C$.

For (ii), consider a shortest simple cycle $C$ in $G$, of length $g$. If there are multiple shortest simple cycles, pick one with the minimum number of non-white vertices. We can express $C$ as a concatenation of simple paths ${\pi }_0^R,{\pi }_0^B,\mathrm{\dots },{\pi }_{k-1}^R,{\pi }_{k-1}^B$ with $k\ge 1$, where each ${\pi }_i^R$ lies in $G[R\cup W]$, uses at least one red vertex, and starts and ends with white vertices, and each ${\pi }_i^B$ lies in $G[B\cup W]$, uses at least one blue vertex, and starts and ends with white vertices. (Note that $C$ contains at least one red and at least one blue vertex, by the assumption in stated in (ii).) If ${\delta }_{G[R\cup W]}(u({\pi }_i^R),v({\pi }_i^R))={\delta }_{G[W]}(u({\pi }_i^R),v({\pi }_i^R))$ for some $i$, then we can replace ${\pi }_i^R$ with a shortest path $\gamma$ from $u({\pi }_i^R)$ to $v({\pi }_i^R)$ in $G[W]$, and obtain a closed walk which is the concatenation of two non-identical simple paths $\gamma$ and $C\setminus {\pi }_i^R$, and so must contain a nontrivial simple cycle; the cycle has length at most $g$ and uses fewer non-white vertices: a contradiction. Thus, each ${\pi }_i^R$ is a legal red path. Similarly, each ${\pi }_i^B$ is a legal blue path. Hence, $C$ is a legal alternating closed walk. $◀$

(An astute reader might wonder why we have overcomplicated the definition of legal alternating walk by including the white subpaths ${\tau }_i$, since part (ii) of the proof of Lemma 4 does not require them. The purpose for including them is computational, as we will see later: without them, intermediate distance matrices may no longer satisfy the bounded-difference property.)