On Thin Perfect Matchings up to Polylogarithmic Factors

AIPR assessment

Problem difficulty is high: this sits in a competitive area of combinatorial optimization and thin structures, with active prior work on thin trees, cut sparsification, and ordinal matching. The strengths reinforce each other well, since the structural tree-cut insight, the constructive greedy pairing, and the metric-distortion application all point in the same direction. The weaknesses are milder but compounding in the sense that the support-constrained bound remains far from constant, the rela

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.

Score Breakdown

More from this week

• Towards Interactive Video World Modeling: Frontiers, Challenges, Benchmarks, and Future Trends
• ViBE: Co-Optimizing Workload Skew and Hardware Variability for MoE Serving
• LeAP: Learnable Adaptive Permutation for Feature Selection in Heterogeneous and Sparse Recommender Systems
• PolySpeech-100: A Large-Scale Benchmark for Speech Understanding Across 100+ Languages and Dialects
• HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces

More in Discrete Mathematics

• \(\mathit{SB}(3,n)\) has no Hamiltonian cycle when \(n\) is even: a sign-of-permutation proof, with extension to all odd \(m\equiv 3\pmod 4\)
• Weak Order on the MacNeille Completion of Bruhat Order
• A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
• Hamilton decompositions of the directed 7-torus at odd modulus via root-flat certificates and a prefix-count construction
• Succinct Graph Representations and Algorithmic Applications