On Computing an Optimal Semi-matching

A semi‐matching in a bipartite graph $G=(U,V,E)$ is a set of edges $M\subseteq E$ such that each vertex in U is incident to exactly one edge in M, i.e., $de{g}_M(u)=1$ for each $u\in U$ . An optimal semi‐matching is a semi‐matching with the minimal value of the cost function ${\sum }_{v\in V}\frac{de{g}_M(v)·(de{g}_M(v)+1)}{2}$ . Exploiting the divide‐and‐conquer nature of the semi‐matching problem, we reduce the problem to a simpler problem whose objective is to compute a maximum weak bounded‐degree semi‐matching. Using the reduction we derive three algorithms for the optimal semi‐matching problem. The first one runs in time $O(\sqrt{n}·m·logn)$ on a graph with n vertices and m edges. The second one is randomized and computes an optimal semi‐matching with high probability in time $O(n^{\mathit{\omega }}·{log}^{1+o(1)}n)$ , where $\mathit{\omega }$ is the exponent of the best known matrix multiplication algorithm. Since $\mathit{\omega }<2.38$ , this algorithm breaks through $O(n^{2.5})$ barrier for dense graphs. In the case of planar graphs, the third one computes an optimal semi‐matching in deterministic time $O(n·{log}^{4}n)$ .