Exact Subquadratic Algorithm for Many-To-Many Matching on Planar Point Sets with Integer Coordinates

The prism graph $\tilde{G}$ is a two-layered bipartite graph consisting of an “upper” layer, which is the original graph $G$, and a “lower” layer, which is a mirrored copy $\widehat{G}$ of $G$. For each vertex $v$ in the upper layer, we add a link edge between $v$ and its corresponding copy $\widehat{v}$ in the lower layer. Note that $\tilde{G}$ remains bipartite, as its vertex set can be partitioned into $R\cup \{\widehat{v}\mid \widehat{v}\text{ is the copy of }v\in B\}$ and $B\cup \{\widehat{v}\mid \widehat{v}\text{ is the copy of }v\in R\}$. See Figure 1. For an edge $e=(u,v)$ in $\tilde{G}$, the cost $\tilde{c}(e)$ is defined as follows:

• $\mathrm{■}$

  If $u$ and $v$ are both in the upper layer, $\tilde{c}(e)=\Vert u-v\Vert$.

• $\mathrm{■}$

  If $u$ and $v$ are both in the lower layer, $\tilde{c}(e)=0$.

• $\mathrm{■}$

  If $e$ is a link edge $(v,\widehat{v})$, $\tilde{c}(e)=\mu (v)$, where $\mu (v)$ is the distance from $v$ to its nearest neighbor in the opposite set ($R$ or $B$).

Note that an optimal edge cover $M$ of $G$ consists of disjoint stars. For a star of $M$ of size larger than two, let $c$ be the center of the star. Then for every vertex of the star other than $c$, its closest neighbor in the opposite set is $c$. Otherwise, we can reconnect it with its closest neighbor without violating the feasibility of the solution. This reduces the problem into the minimum-cost matching problem with penalties where the penalty of each point is $\mu (\cdot )$. The construction of the prism graph is based on this intuition. Matching a vertex via a link edge to the lower layer simulates leaving that vertex uncovered by the primary matching in the upper layer, instead paying the penalty of connecting it to its nearest neighbor.

The values $\mu (v)$ for all $v\in R\cup B$ can be computed in $O(n\log n)$ time by constructing the Voronoi diagrams of $R$ and $B$ and using a planar point location data structure [14]. Although $\tilde{G}$ has $\mathrm{\Theta }(n^2)$ edges in the worst case, we can store it using complexity of $O(n)$ by maintaining only the vertices and the link edges explicitly. The edges in $G$ and $\widehat{G}$ can be represented implicitly as they form complete bipartite graphs.

The following lemma establishes the equivalence between the minimum-cost edge cover of $G$ and the minimum-cost perfect matching of $\tilde{G}$. For illustration, see Figure 1.

Due to the lack of space, some proofs are omitted. The missing proofs can be found in the full version of this paper.

We use induction on the points of $B\cup R$ encountered from left to right. Let $x_0$ be a point to the left of the leftmost point of $B\cup R$. We define $F_{x_0}(0)=0$ and $F_{x_0}(k)=\mathrm{\infty }$ for $k\ne 0$, which is trivially convex.

Let $p\in B\cup R$ be the current point and $p^{\prime }$ be the previous point in $B\cup R\cup \{x_0\}$. Let $d=\Vert p-p^{\prime }\Vert$. Without loss of generality, assume that $p\in B$. By the induction hypothesis, $F_{p^{\prime }}(\cdot )$ is convex. Note that $|k-1|d$ is a convex function of $k$. Since the sum of two convex functions is also convex, $F_{p^{\prime }}(k-1)+|k-1|d$ is convex. Similarly, $F_{p^{\prime }}(k)+|k|d+w_p$ is convex. Although the minimum of two convex functions is not convex in general, it is convex in our setting. This holds due to the following claim with $f(k)=F_{p^{\prime }}(k)+|k|d$.

Therefore, the lemma holds for any fixed point $x\in R\cup B$. $◀$

As we showed in the proof of Claim 6, the following corollary holds.

Fix $x\in \mathrm{\ell }$, and let $\mathrm{\Delta }{F}_x(k):=F_x(k)-F_x(k-1)$. We maintain $F_x(0)$ and $\mathrm{\Delta }{F}_x(k)$ for all indices $k$. Note that they fully represent $F_x(\cdot )$. To make the update efficiently, we store $\mathrm{\Delta }{F}_x(\cdot )$ using two balanced binary search trees. Let $H_x^{+}$ and $H_x^{-}$ be two sets where

Since $F_x(\cdot )$ is convex, $\mathrm{\Delta }{F}_x(k)$ is non-decreasing with respect to $k$. We maintain the two sets using two binary search trees $T_x^{+}$ and $T_x^{-}$ and offsets $o^{+}$ and $o^{-}$. The offsets allow us to shift all stored values uniformly without updating each element explicitly. Each leaf of a tree of $T_x^{+}$ (and $T_x^{-}$) corresponds to exactly one index $k>0$ (and ), and the leaf stores the value $\mathrm{\Delta }{F}_x(k)-o^{+}$ (and $\mathrm{\Delta }{F}_x(k)-o^{-}$). Thus, the actual value of $\mathrm{\Delta }{F}_x(k)$ is obtained by adding the corresponding offset $o^{+}$ or $o^{-}$. Each internal node additionally stores the size of its subtree and the sum of the stored values in its subtree (excluding the offset). Hence, the true sum of the values in any subtree can be obtained by adding the offset multiplied by the subtree size. The leaves of $T_x^{+}$ (and $T_x^{-}$) are stored in increasing order of their indices $k$. Since $F_x(\cdot )$ is convex, the stored values are non-decreasing along this order. Therefore, $T_x^{+}$ and $T_x^{-}$ can be implemented as binary search trees augmented with subtree sizes and subtree sums, supporting insertion, deletion, and prefix-sum queries in $O(\log n)$ time. We call the tuple of $F_x(0)$, $o^{+}$, $o^{-}$, $T_x^{+}$ and $T_x^{-}$ the representation of $F_x(\cdot )$. Here, since the roots store the size of the trees, we do not need to explicitly maintain $\text{dom}(F_p)$.

We show how to compute $F_x(k)$ for any integer $k>0$. For $k=0$, we maintain $F_x(0)$ explicitly, and for , we can do this symmetrically. By telescoping, we have

Thus, it suffices to compute the prefix sum of the first $k$ values in $H_x^{+}$.

Since $\mathrm{\Delta }{F}_x(k)$ is non-decreasing in $k$, the values stored in $T_x^{+}$ are already ordered by index. We augment each node of $T_x^{+}$ with the size of its subtree and the sum of the stored values in its subtree (excluding the offset $o^{+}$). Using standard binary search tree operations, we can retrieve the sum of the smallest $k$ elements in $T_x^{+}$ in $O(\log n)$ time. Adding this sum and the accumulated offset $k\cdot o^{+}$ to $F_x(0)$ yields $F_x(k)$. Therefore, given the representation of $F_x(\cdot )$, we can compute $F_x(k)$ for any integer $k$ in $O(\log n)$ time. $◀$

Assume that we are given the representation of $F_{p^{\prime }}(\cdot )$, and we wish to compute the representation of $F_p(\cdot )$, where $p$ is the next point to the right of $p^{\prime }$ on $\mathrm{\ell }$. We describe the case $p\in B$; the case $p\in R$ is symmetric. Let $d:=\Vert p-p^{\prime }\Vert$.

We first consider the transportation cost. Let $f(k):=F_{p^{\prime }}(k)+|k|d$. Thus, before handling the matching/penalty decision at $p$, we first transform the representation of $F_{p^{\prime }}$ into the representation of $f$. For $k>0$, we have $\mathrm{\Delta }f(k)=\mathrm{\Delta }{F}_{p^{\prime }}(k)+d$, and for $k\le 0$, we have $\mathrm{\Delta }f(k)=\mathrm{\Delta }{F}_{p^{\prime }}(k)-d$. Hence, this update can be performed by increasing the offset $o^{+}$ by $d$, and decreasing the offset $o^{-}$ by $d$, while keeping the trees unchanged. Also, $F_{p^{\prime }}(0)$ remains unchanged since $|0|d=0$. After this step, the representation corresponds to $f(\cdot )$.

We then find the largest integer $k^{\ast }$ with $\mathrm{\Delta }f(k)\le -w_p$ by a binary search over the ordered trees $T_{p^{\prime }}^{+}$ and $T_{p^{\prime }}^{-}$ in $O(\log n)$ time. Since $\mathrm{\Delta }f(k)$ is non-decreasing in $k$, the threshold $k^{\ast }$ can be found by searching for the largest index whose discrete derivative is at most $-w_p$. Recall that $F_p(k)=\min \{f(k-1),f(k)+w_p\}$ from (1). By Corollary 7, for $k\le k^{\ast }$, we have $F_p(k)=f(k)+w_p$, and for $k>k^{\ast }$, we have $F_p(k)=f(k-1)$.

We now update the representation of $f(\cdot )$ to obtain that of $F_p(\cdot )$. We first compute $F_p(0)$. Since $F_p(0)=\min \{f(-1),f(0)+w_p\}$, this value can be computed in $O(\log n)$ time using Observation 8.

We next determine the new discrete derivatives. For $k\le k^{\ast }$, both $F_p(k)$ and $F_p(k-1)$ lie in the same case, and hence

For $k>k^{\ast }+1$, we have

At the boundary $k=k^{\ast }+1$, we have

Therefore, the sequence $\mathrm{\Delta }{F}_p(\cdot )$ is obtained from $\mathrm{\Delta }f(\cdot )$ by inserting the single value $-w_p$ (minus the corresponding offset) at position $k^{\ast }+1$. As a result, all indices strictly larger than $k^{\ast }$ are shifted by one position to the right.

Since the discrete derivatives are stored in a binary search tree, this transformation can be implemented by a single rank-based insertion at index $k^{\ast }+1$. If , the insertion shifts the element originally at index $0$ to index $1$. Because index $0$ belongs to $T_{p^{\prime }}^{-}$ and index $1$ belongs to $T_{p^{\prime }}^{+}$, we must extract the maximum element from $T_{p^{\prime }}^{-}$ and insert it as the minimum element in $T_{p^{\prime }}^{+}$ (after adjusting the values with respect to the offsets for the two trees). All subtree sizes and subtree sums are updated along the search path. The insertion and any necessary boundary shifts take $O(\log n)$ time. Thus, the entire update from the representation of $F_{p^{\prime }}(\cdot )$ to that of $F_p(\cdot )$ takes $O(\log n)$ time.

We consider the points of $B\cup R$ from left to right. The initialization takes $O(n)$ time, and each update takes $O(\log n)$ time. Therefore, the total running time is $O(n\log n)$.

We define the scaled dual weight of a vertex $v\in \tilde{V}$ as $y_{\theta }(v)=\theta \cdot y(v)$. The following lemma establishes a lower bound on the sum of scaled dual weights for the edges participating in an optimal matching of $\tilde{G}$.

The proof is same as the argument in [20] and is thus omitted. We define the set of eligible edges, denoted by $E_{\text{elig}}$, as the set of all edges in the upper layer of $\tilde{G}$ satisfying the condition (4). Lemma 10 implies that for any optimal matching ${\tilde{M}}^{\ast }$ of $\tilde{G}$, all edges of ${\tilde{M}}^{\ast }$ that belong to the upper layer are contained in $E_{\text{elig}}$. Therefore, even if we remove all non-eligible edges in the upper layer from the prism graph, the optimal solution remains the same.

The following lemma shows that if no four vertices of $R\cup B$ are collinear, then the graph obtained from the upper layer of the prism graph by removing all non-eligible edges is planar. Thus our main focus is to handle collinear points in the following.

We show that the non-crossing property enables us to compute an eligible edge decomposition $P=\{(p_1,q_1),\mathrm{\dots },(p_k,q_k)\}$, which is a set of non-crossing line segments, such that for every edge of $E_{\text{elig}}$, it is contained in a segment of $P$. Note that $P$ induces a plane graph whose vertices come from $R\cup B$.

Since the definition of eligible edges in our setting is identical to that in Sharathkumar [20], we can adopt their algorithm for computing the eligible edge decomposition. However, a minor technical hurdle arises in the initialization phase. It uses an approximate perfect matching $M$ obtained from the first phase, but in our setting, an approximate matching we have is not necessarily perfect if we look at the upper layer only. More specifically, it first computes all point-line pairs $(p,\mathrm{\ell })$ with $p\in R\cup B$ such that $\mathrm{\ell }$ contains an eligible edge incident to $p$. The number of such pairs is $O(n)$. For a point $p\in R\cup B$, one can compute all eligible edges incident to it in $O(\mathrm{polylog}n)$ time per edge using a dynamic weighted nearest neighbor data structure. However, it is possible that a single line $\mathrm{\ell }$ contains many different eligible edges incident to $p$. Then a single line can be discovered multiple times, which leads to quadratic running time in the worst case. To avoid this, as initialization, it computes just one line $\mathrm{\ell }$ for each point $p$ in $R\cup B$ containing an eligible edge incident to $p$ in $O(n\mathrm{polylog}n)$ time in total using $M$. Later, it considers each point $p$ in $B\cup R$ one by one and computes all pairs $(p,\mathrm{\ell })$ such that $\mathrm{\ell }$ is not found in the initialization. Even in this case, a single line $\mathrm{\ell }$ can be discovered multiple times, but the total number of pairs $(p,\mathrm{\ell })$ found in this way is $O(n)$, which leads to near-linear running time. The perfect matching $M$ can be used in the initialization; since an edge $(u,v)$ of $M$ is eligible, its extension contains an eligible edge incident to $u$ (and $v$). But we can perform this initialization using a dynamic weighted nearest-neighbor data structure, and this does not increase the overall running time. The full details of this modified construction are deferred to the full version of this paper.

We now construct the candidate edge set ${\tilde{E}}_{\text{cand}}$ of size $O(n)$ using the eligible edge decomposition $P$. As mentioned earlier, if no four points of $R\cup B$ are collinear, we can simply construct ${\tilde{E}}_{\text{cand}}$ by adding all eligible edges (the edges of $P$), their mirrored edges in the lower layer, and all link edges between the layers. However, in the general case, the number of eligible edges can be $\mathrm{\Theta }(n^2)$, making it impossible to include all of them.

Instead, we select a restricted subset of eligible edges as follows. For each pair $(p,q)\in P$, let $I$ be the set of points in $R\cup B$ lying on the open segment between $p$ and $q$. For a minimum-cost perfect matching ${\tilde{M}}^{\ast }$ of $\tilde{G}$, any edge incident to a vertex $v\in I$ must have its other endpoint in $I\cup \{\widehat{v},p,q\}$. Consequently, for the endpoints $p$ and $q$, there are four possible configurations based on whether $p$ and $q$ are matched with points in $I$. For each configuration, we can identify the specific edges of ${\tilde{M}}^{\ast }$ incident to points in $I$ in $O(|I|\log |I|)$ time without computing the entire matching. More specifically, let $I^{\prime }\subseteq \{p,q\}$ be the set of points matched with elements in $I$ under ${\tilde{M}}^{\ast }$. By solving the local matching problem for $I\cup I^{\prime }$, we extract the necessary edges to be included in ${\tilde{E}}_{\text{cand}}$, ensuring the total size remains $O(n)$. For the local matching problem, since the vertices of $I\cup I^{\prime }$ are collinear, the problem is restricted to one dimension. This problem reduces to the minimum-cost matching problem on $I\cup I^{\prime }$, where leaving a vertex unmatched incurs a penalty of ${\mu }^{\prime }(\cdot )$, where ${\mu }^{\prime }(v)=\mu (v)$ for a vertex $v\in I$ and ${\mu }^{\prime }(v)=\mathrm{\infty }$ for a vertex $v\in I^{\prime }$. Therefore, the local matching problem can be solved in $O(|I|\log |I|)$ time by Theorem 2. We do this for all the four configurations, and then take the union of the resulting edges. Then ${\tilde{E}}_{\text{cand}}$ is defined as the union of all such edges in $P$, their mirrored edges in the lower layer, and all the link edges. Then the size of ${\tilde{E}}_{\text{cand}}$ is $O(n)$, and it can be computed in $O(n\log n)$ time.

We show that ${\tilde{E}}_{\text{cand}}$ contains a minimum-cost perfect matching of $\tilde{G}$. For this, we use the following technical lemma justifying that focusing on the upper layer during the construction of ${\tilde{E}}_{\text{cand}}$ is sufficient. We say a matching $M$ is symmetric if an edge $(u,v)$ in the upper layer is contained in $M$ if and only if its mirrored edge $(\widehat{u},\widehat{v})$ is contained in $M$.

Let ${\tilde{M}}^{\ast }$ be an arbitrary minimum-cost perfect matching of $\tilde{H}$. Let $m$ be the number of edges in ${\tilde{M}}^{\ast }$ that belong to the upper layer. Each such edge $(u,v)$ covers one vertex in $R$ and one in $B$. Because ${\tilde{M}}^{\ast }$ is a perfect matching, any vertex in the upper layer not matched with a vertex in the upper layer must be matched to its corresponding copy in the lower layer via a link edge. This implies that exactly $m$ vertices in the lower layer are not covered by link edges. To satisfy the perfect matching requirement, these $m$ vertices must be matched to each other using $m/2$ edges in the lower layer.

Now, consider the cost of these $m/2$ edges. By construction, the cost of any edge in the lower layer is zero. Therefore, we can replace the existing lower-layer edges in ${\tilde{M}}^{\ast }$ with the “mirrored” edges of the upper-layer matching without changing the total cost of the matching. This substitution results in a new perfect matching $M^{\prime }$ that remains optimal and satisfies the symmetry condition: $(u,v)$ is in $M^{\prime }$ if and only if $(\widehat{u},\widehat{v})$ is in $M^{\prime }$. Therefore, the lemma holds. $◀$

Let ${\tilde{M}}^{\ast }$ be a minimum-cost perfect matching of $\tilde{G}$ such that (i) all edges of ${\tilde{M}}^{\ast }$ belonging to the upper layer are contained in $E_{\text{elig}}$, and (ii) ${\tilde{M}}^{\ast }$ is symmetric, which always exists by Lemma 10 and by Lemma 12.

To show that ${\tilde{M}}^{\ast }\subseteq {\tilde{E}}_{\text{cand}}$, we consider the eligible edge decomposition $P$. Every edge $(u,v)\in {\tilde{M}}^{\ast }$ in the upper layer must be contained within some segment $\overline{pq}\in P$. For each such segment, let $I$ be the set of points of $B\cup R$ lying in the open interval between $p$ and $q$. By the construction of $P$, any edge in ${\tilde{M}}^{\ast }$ incident to a vertex in $I$ must have its other endpoint in $I\cup \{\widehat{v},p,q\}$. This local constraint implies that the matching within each segment $\overline{pq}$ can be optimized independently based on the four possible configurations of the endpoints $p$ and $q$. Since ${\tilde{E}}_{\text{cand}}$ is constructed by taking the union of the optimal local matchings for all four configurations across all segments in $P$, it follows that the edges of ${\tilde{M}}^{\ast }$ are included in ${\tilde{E}}_{\text{cand}}$. Thus, the subgraph of $\tilde{G}$ induced by ${\tilde{E}}_{\text{cand}}$ contains a minimum-cost perfect matching of $\tilde{G}$. $◀$

Therefore, the candidate edge set ${\tilde{E}}_{\text{cand}}$ can be computed in $\tilde{O}(n)$ time in total, and the problem reduces to computing a minimum-cost perfect matching on the subgraph ${\tilde{G}}_{\text{cand}}$ of $\tilde{G}$ induced by ${\tilde{E}}_{\text{cand}}$. For an illustration of ${\tilde{G}}_{\text{cand}}$, see Figure 2.

It is worth noting the structural distinction between our construction and the one-to-one setting addressed by Sharathkumar [20]. In the one-to-one case, for each segment $(p,q)\in P$, it is sufficient to consider at most two configurations of the endpoints $p$ and $q$, which makes the resulting graph planar. This is because the difference between the numbers of points in $R$ and of points in $B$ restricts the possible configurations of $p$ and $q$. In the many-to-many setting, however, this difference does not inherently reduce the number of configurations. Consequently, we must consider the union of local optimal matchings for all four configurations, which renders the resulting candidate graph ${\tilde{G}}_{\text{cand}}$ non-planar.

We prove this by examining the three types of edges $e$ in ${\tilde{E}}_{\text{cand}}$. In the first case that $e$ belongs to the upper layer, every eligible edge in the upper layer is contained in a segment $s$ in $P$. If an endpoint of $s$ is contained in $X$ (or in $Y$), both endpoints of $e$ are in $\tilde{X}$ (or $\tilde{Y}$), or one belongs to $\tilde{X}$ (or $\tilde{Y}$) and the other to $\tilde{S}$. If both endpoints of $s$ are contained in $S$, both endpoints of $e$ are contained in $\tilde{S}$. Thus in any case, the lemma holds.

In the other cases, the lemma holds due to the symmetric construction of ${\tilde{E}}_{\text{cand}}$ following Lemma 12. Specifically, a vertex $v\in B\cup R$ and its copy $\widehat{v}$ belong to the same set among $\tilde{X},\tilde{Y}$ and $\tilde{S}$. Therefore, in the case that $e$ belongs to the lower layer, or $e$ is a link edge, the lemma holds immediately. $◀$ We refer to $\tilde{S}$ as the prism separator of ${\tilde{G}}_{\text{cand}}$. We classify each vertex of the prism separator $\tilde{S}$ into two types. We call a vertex of $S\cup \widehat{S}$ a skeleton vertex of $\tilde{S}$ and a vertex of $\tilde{S}\setminus (S\cup \widehat{S})$ an interior vertex of $\tilde{S}$. See Figure 2.

We now present a detailed divide-and-conquer algorithm for computing a minimum-cost perfect matching of ${\tilde{G}}_{\text{cand}}$. The algorithm first computes the partition $(\tilde{X},\tilde{Y},\tilde{S})$ of the vertex set in linear time and recursively finds minimum-cost perfect matchings for the subgraphs induced by $\tilde{X}$ and $\tilde{Y}$. Note that the subgraph induced by $\tilde{X}$ (and $\tilde{Y}$) has a perfect matching due to its prism structure. Since no edges connect $\tilde{X}$ and $\tilde{Y}$, the union of their optimal matchings is a minimum-cost perfect matching for the subgraph induced by $\tilde{X}\cup \tilde{Y}$. To obtain the optimal matching for the entire graph, one might consider extending this matching by adding all vertices of the separator $\tilde{S}$ one by one using the following lemma. Here, a minimum-cost maximum-cardinality matching is defined as the matching with the minimum total cost among all matchings of maximum possible cardinality.

However, a naive application of Lemma 17 to all vertices in $\tilde{S}$ would take $O(|\tilde{S}|\cdot n\log n)$ time, which is inefficient since $|\tilde{S}|$ can be as large as $\mathrm{\Theta }(n)$. To address this, we observe that $\tilde{S}$ consists of $O(\sqrt{n})$ skeleton vertices and a potentially large number of interior vertices. Our strategy is to handle the skeleton vertices using Lemma 17, while the interior vertices are handled efficiently by exploiting their 1D nature and pre-computed optimal matchings.

The algorithm processes the subgraph ${\tilde{G}}^{\prime }$ of ${\tilde{G}}_{\text{cand}}$ in each recursive step as follows. Using the subgraph of $G(P)$ induced by $V(P)\cap V({\tilde{G}}^{\prime })$, we compute a balanced separator $S$ and a partition $(\tilde{X},\tilde{Y},\tilde{S})$ of ${\tilde{G}}^{\prime }$. As mentioned earlier, we compute a minimum-cost perfect matching of $\tilde{X}\cup \tilde{Y}$ in linear time. Now consider the internal vertices of $\tilde{S}$. We decompose them into subsets such that each subset consists of the internal vertices lying on the same segment of $P$. For each subset $W$, we retrieve its optimal matching of $W\cup \widehat{W}$ using the pre-computed 1D matching from Section 4.1, where $\widehat{W}$ is the copy of $W$ in the lower layer. An optimal matching of $W\cup \widehat{W}$ can be obtained from a minimum-cost matching of $W$ with penalties, which can be found in near-linear time. Since no edge of ${\tilde{G}}^{\prime }$ connects two vertices from different subsets, the union $M^{\prime }$ of the all these matchings is a minimum-cost maximum-cardinality matching of $\tilde{X}\cup \tilde{Y}\cup \{\text{internal vertices of }\tilde{S}\}$. Finally, we reintroduce the $O(\sqrt{n^{\prime }})$ skeleton vertices of $\tilde{S}$ into the matching using Lemma 17, where $n^{\prime }=|V({\tilde{G}}^{\prime })\cap V(P)|$. We iteratively apply Lemma 17 for each skeleton vertex of $\tilde{S}$ to update ${\tilde{M}}^{\prime }$. In this way, each recursion step takes $\tilde{O}(|V({\tilde{G}}^{\prime })|\sqrt{n^{\prime }})$ time in total.

In the base case that the number of (skeleton) vertices of $V(P)\cap V({\tilde{G}}^{\prime })$ is $O(1)$, we compute a minimum-cost maximum-cardinality matching of the (non-skeleton) vertices of $V({\tilde{G}}^{\prime })\setminus V(P)$ using their 1D nature in $\tilde{O}(|V({\tilde{G}}^{\prime })|)$ time. Then we reintroduce the $O(1)$ skeleton vertices with Lemma 17. This takes $\tilde{O}(|V({\tilde{G}}^{\prime })|)$ time in total.

To bound the overall time complexity, let $\eta =O(n)$ be the number of vertices of $V(P)$. At depth $d$ of the recursion, let $H_{d,1},H_{d,2},\mathrm{\dots }$ denote the disjoint subgraphs, where each $H_{d,i}$ contains $m_{d,i}$ edges and ${\eta }_{d,i}$ skeleton vertices along with their copies. By Theorem 14 and Observation 15, the number of skeleton vertices shrinks by a factor of at least $2/3$ per level, yielding ${\eta }_{d,i}\le {(2/3)}^d\eta$. Furthermore, since the subgraphs at any depth are edge-disjoint, ${\sum }_i{m}_{d,i}\le |{\tilde{E}}_{\text{cand}}|=O(n)$.

In the conquer phase, merging the sub-solutions for $H_{d,i}$ requires $O(\sqrt{{\eta }_{d,i}})$ augmentations. Since each augmentation takes $O(m_{d,i}\log n)$ time by Lemma 17, the total time for depth $d$ is:

Because , the time for each level decreases geometrically. The total running time of the divide-and-conquer algorithm is thus dominated by the root level, which is $O(n^{1.5}\log n)$.

We compute an approximate matching and its dual weights for the scaled graph with a suitable scaling factor in $\tilde{O}(n^{1.5}\log \mathrm{\Delta })$ time. The candidate graph can be computed in $O(n\log n)$ time, and the divide-and-conquer algorithm takes $O(n^{1.5}\log n)$ time. Therefore, the total time complexity of our algorithm remains $\tilde{O}(n^{1.5}\log \mathrm{\Delta })$.