Geometric Bipartite Matching is in NC
<|reference_start|>Geometric Bipartite Matching is in NC: In this work, we study the parallel complexity of the Euclidean minimum-weight perfect matching (EWPM) problem. Here our graph is the complete bipartite graph $G$ on two sets of points $A$ and $B$ in $\mathbb{R}^2$ and the weight of each edge is the Euclidean distance between the corresponding points. The weighted perfect matching problem on general bipartite graphs is known to be in RNC [Mulmuley, Vazirani, and Vazirani, 1987], and Quasi-NC [Fenner, Gurjar, and Thierauf, 2016]. 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 for EWPM, a linear number of bits of approximation is required to distinguish between the minimum-weight perfect matching and other perfect matchings. Next, we show that the EWPM problem that allows up to $\frac{1}{poly(n)}$ additive error, is in NC.<|reference_end|>
@article{bhore2024geometric,
    title={Geometric Bipartite Matching is in NC},
    author={Sujoy Bhore, Sarfaraz Equbal, Rohit Gurjar},
    journal={arXiv preprint arXiv:2405.18833},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.18833},
    primaryClass={cs.CG cs.CC}
}