Parallel Complexity of Geometric Bipartite Matching

Sujoy Bhore, Sarfaraz Equbal, Rohit GurjarFSTTCS 2024 · OpenReview

TL;DR

This paper investigates the parallel computational complexity of finding the minimum-weight perfect matching in a geometric bipartite graph. The authors prove a lower bound showing that distinguishing the optimal matching requires significant bit precision, and then present an efficient parallel algorithm (in NC) that finds a near-optimal matching with a small additive error.

What Problem Does This Paper Address?

The core problem is finding a Geometric Minimum-Weight Bipartite Perfect Matching (GWBPM). Imagine you have two sets of points, A and B, scattered in a 2D plane. You want to pair up every point in A with a unique point in B such that the total "cost" of these pairings is minimized. The cost of pairing two points is defined as the Euclidean distance between them (specifically, the $l_p$ distance for any $p \ge 2$).

While finding perfect matchings in general graphs has seen significant progress in parallel computation (reaching RNC and even Quasi-NC), the geometric version, especially for exact minimum weight, remains a challenge. A key question is whether this problem can be solved efficiently in parallel using only deterministic algorithms (i.e., in the class NC), which would be a major theoretical advancement. The paper also touches upon the practical implications of using limited precision for distances in computational geometry.

Methods

The paper tackles the problem from two angles: a lower bound and an upper bound (an algorithm).

Lower Bound: To show that an exact NC algorithm is unlikely without significant approximations, the authors construct specific geometric point configurations. They leverage a technique similar to the pigeonhole principle to create scenarios where the minimum-weight perfect matching and the next-best matching have weights that are extremely close. This closeness implies that distinguishing the true minimum requires a very high degree of precision in calculating distances, making it hard for standard parallel algorithms that rely on polynomially bounded weights.

Upper Bound (NC Algorithm): The main contribution is an NC algorithm for finding an approximate GWBPM. The strategy involves:

  1. Approximate Distances: Instead of using exact $l_p$ distances, they use approximations with a controlled number of bits. This is crucial for making computations feasible in parallel.
  2. Weight Scheme: They combine an approximate distance function with a specific "isolating weight assignment" function ($W_{TV}$) originally designed for planar graphs. This combined weight function is designed to ensure that the minimum-weight matching under this scheme is unique and corresponds to a near-optimal matching in the original problem.
  3. Planarity Argument: A key insight is that the union of near-minimum weight perfect matchings in a geometric bipartite graph forms a planar subgraph. This allows them to adapt techniques developed for planar graphs.
  4. MVV Algorithm: Finally, they leverage the Mulmuley-Vazirani-Vazirani (MVV) algorithm, which can find a minimum-weight perfect matching in NC given an isolating weight assignment with polynomially bounded bits.

Datasets

Not discussed in the paper. The problem is theoretical and deals with abstract geometric point sets rather than specific datasets.

Key Insights and Ideas

  • Precision Matters: The paper strongly suggests that achieving an exact minimum-weight geometric bipartite matching in parallel (NC) is likely impossible without using a super-linear number of bits to represent distances. This highlights a fundamental limitation of parallel computation for geometric optimization problems.
  • Approximation is Key: The path to an NC algorithm for GWBPM lies in accepting a small additive error. By approximating distances, they can construct a weight function that is "isolating" and amenable to existing parallel algorithms.
  • Planarity as a Tool: The surprising insight that the union of near-optimal matchings forms a planar graph is crucial. This allows them to leverage existing, powerful techniques for planar graph problems.
  • Combining Techniques: The paper elegantly combines geometric constructions, approximation theory, and established parallel algorithms (like MVV) to solve a challenging problem.

Key Results

  • Lower Bound: For GWBPM under $l_p$ metric ($p \ge 2$), distinguishing the minimum-weight perfect matching from others requires $\Omega(n \log n)$ bits of approximation for weights.
  • NC Algorithm: An NC algorithm is presented that solves the $\delta$-GWBPM problem (finding a matching with weight at most $w^* + \delta$, where $w^*$ is the optimal weight and $\delta = 1/\text{poly}(n)$) for points on a polynomially bounded integer grid. This means a near-optimal solution can be found efficiently in parallel.

Limitations and Future Work

  • Approximation: The primary limitation is that the presented NC algorithm provides an approximate solution, not an exact one. The lower bound suggests that an exact solution in NC might be unattainable.
  • Non-Bipartite Case: The paper focuses on bipartite matching. A natural open question is whether the non-bipartite version of GWBPM can also be solved in NC.
  • Higher Dimensions: The current work is for 2D geometric bipartite matching. Extending these results to 3 or higher dimensions is a potential future direction.
  • Bit Complexity: While the algorithm is in NC, the number of bits required for coordinates and weights is polynomial in $n$ and depends on the approximation factor $\delta$. Further analysis of bit complexity might be warranted.

Summary updated

Abstract

In this work, we study the parallel complexity of the geometric minimum-weight bipartite perfect matching (GWBPM) problem in ℝ². Here our graph is the complete bipartite graph G on two sets of points A and B in ℝ² (|A| = |B| = n) and the weight of each edge (a,b) ∈ A × B is the 𝓁_p distance (for some integer p ≥ 2) between the corresponding points, i.e., ||a-b||_p. The objective is to find a minimum weight perfect matching of A∪ B. In their seminal work, Mulmuley, Vazirani, and Vazirani (STOC 1987) showed that the weighted perfect matching problem on general bipartite graphs is in RNC. Almost three decades later, Fenner, Gurjar, and Thierauf (STOC 2016) showed that the problem is in Quasi-NC. Both of these results work only when the weights are of O(log n) bits. It is a long-standing open question to show the problem to be in NC. First, we show that in a geometric bipartite graph under the 𝓁_p metric for any p ≥ 2, unless we take Ω(n) bits of approximation for weights, we cannot distinguish the minimum-weight perfect matching from other perfect matchings. This means that we cannot hope for an MVV-like NC/RNC algorithm for solving GWBPM exactly (even when vertex coordinates are small integers). Next, we give an NC algorithm (assuming vertex coordinates are small integers) that solves GWBPM up to 1/poly(n) additive error, under the l_p metric for any p ≥ 2.
BibTeX
@inproceedings{bhore2024parallel,
  author = {Sujoy Bhore and Sarfaraz Equbal and Rohit Gurjar},
  title = {{Parallel Complexity of Geometric Bipartite Matching}},
  booktitle = {FSTTCS},
  year = {2024},
  url = {https://openreview.net/forum?id=E02vTZiK7p},
}
Figure