English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the well-studied problem of finding a perfect matching in$d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While thebest-known algorithm for general bipartite graphs (due to Hopcroft and Karp)takes $O(m \sqrt{n})$ time, in regular bipartite graphs, a perfect matching isknown to be computable in $O(m)$ time. Very recently, the $O(m)$ bound wasimproved to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$ expected time, an expressionthat is bounded by $\tilde{O}(n^{1.75})$. In this paper, we further improvethis result by giving an $O(\min\{m, \frac{n^2\ln^3 n}{d}\})$ expected timealgorithm for finding a perfect matching in regular bipartite graphs; as afunction of $n$ alone, the algorithm takes expected time $O((n\ln n)^{1.5})$.  To obtain this result, we design and analyze a two-stage sampling scheme thatreduces the problem of finding a perfect matching in a regular bipartite graphto the same problem on a subsampled bipartite graph with $O(n\ln n)$ edges thathas a perfect matching with high probability. The matching is then recoveredusing the Hopcroft-Karp algorithm. While the standard analysis of Hopcroft-Karpgives us an $\tilde{O}(n^{1.5})$ running time, we present a tighter analysisfor our special case that results in the stronger $\tilde{O}(\min\{m,\frac{n^2}{d} \})$ time mentioned earlier.  Our proof of correctness of this sampling scheme uses a new correspondencetheorem between cuts and Hall's theorem ``witnesses'' for a perfect matching ina bipartite graph that we prove. We believe this theorem may be of independentinterest; as another example application, we show that a perfect matching inthe support of an $n \times n$ doubly stochastic matrix with $m$ non-zeroentries can be found in expected time $\tilde{O}(m + n^{1.5})$.

Perfect Matchings in \~O(n^{1.5}) Time in Regular Bipartite Graphs