Abstract
We resolve the thin matching problem proposed by Anari, Charikar, and Ramakrishnan up to polylogarithmic factors. Given a fractional perfect matching $x$, we say a perfect matching $M$ is $\eta$-thin w.r.t. $x$ if for any cut $(S,\bar{S})$, we have $$ |M \cap E(S,\bar{S})| \leq \eta \cdot x(S,\bar{S}). $$
[ACR23] conjectured that for any fractional perfect matching $x$, there exists a perfect matching $M$ which is $O(1)$-thin w.r.t. $x$. First, we show that if $M$ is restricted to be in the support of $x$, then $\eta \geq \Omega(n)$. We complement this by designing an efficient algorithm that outputs an $O(n \log n)$-thin perfect matching where $n$ is the number of vertices.
Then, we relax this constraint and show that for any fractional perfect matching $x$, there is a perfect matching $M$ (not necessarily in the support of $x$) such that $M$ is $\text{polylog}(n)$-thin w.r.t. $x$. All results work for both bipartite and non-bipartite graphs. We also discuss applications to the metric distortion problem.
Blogger's Review: This paper demonstrates the powerful potential of thin perfect matchings through efficient algorithms, particularly in graph theory and its related fields. The introduction of polylogarithmic factors not only enhances the performance of the algorithm but also offers new insights for solving practical problems, warranting further exploration and application.