{"ID":2921796,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T05:56:00.181519634Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.01330","arxiv_id":"2606.01330","title":"On Thin Perfect Matchings up to Polylogarithmic Factors","abstract":"We resolve the thin matching problem proposed by Anari, Charikar and Ramakrishnan [ACR23] up to polylogarithmic factors. Given a fractional perfect matching $x$, we say a perfect matching $M$ is $α$-thin w.r.t. $x$ if for any cut $(S,\\overline{S})$, we have $$ |M \\cap E(S,\\overline{S})| \\leq α\\cdot x(S,\\overline{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 $α\\geq Ω(n)$ and 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$ (which is 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.","short_abstract":"We resolve the thin matching problem proposed by Anari, Charikar and Ramakrishnan [ACR23] up to polylogarithmic factors. Given a fractional perfect matching $x$, we say a perfect matching $M$ is $α$-thin w.r.t. $x$ if for any cut $(S,\\overline{S})$, we have $$ |M \\cap E(S,\\overline{S})| \\leq α\\cdot x(S,\\overline{S}).$$...","url_abs":"https://arxiv.org/abs/2606.01330","url_pdf":"https://arxiv.org/pdf/2606.01330v1","authors":"[\"Alireza Haqi\",\"Shayan Oveis Gharan\"]","published":"2026-05-31T16:31:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}