We prove a lower bound on the space complexity of two-pass semi-streaming algorithms that approximate the maximum matching problem. The lower bound is parameterized by the density of Ruzsa-Szemeredi graphs: * Any two-pass semi-streaming algorithm for maximum matching has approximation ratio at least $(1- \Omega(\frac{\log{RS(n)}}{\log{n}}))$, where $RS(n)$ denotes the maximum number of induced matchings of size $\Theta(n)$ in any $n$-vertex graph, i.e., the largest density of a Ruzsa-Szemeredi graph. Currently, it is known that $n^{\Omega(1/\!\log\log{n})} \leq RS(n) \leq \frac{n}{2^{O(\log^*{\!(n)})}}$ and closing this (large) gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics. Under the plausible hypothesis that $RS(n) = n^{\Omega(1)}$, our lower bound is the first to rule out small-constant approximation two-pass semi-streaming algorithms for the maximum matching problem, making progress on a longstanding open question in the graph streaming literature.
翻译:近似最大匹配问题的双过半流算法的空间复杂性,我们证明其比重较低。下限由鲁萨-Szemeredi图的密度参数化:* 任何双过半流最大匹配算法的近似比率至少为$(1- \ omega (\ frac\ log{RS(n)\ log{ log{ log{ n ⁇ } } 美元), 其中 $RS(n) 表示大小为$\ Theta(n) 的最大诱导匹配次数 $\ Theta(n) 。 在任何美元/ vertex 图中, 即鲁萨- Szemeredi 图的最大密度。 目前已知 $ ⁇ Omega (1/\\\\\\\ log\ log\ { n}}}\leq RS(n) RS (n) spregroupl) 中, 上下层和下层平面的平面图中, 最下层的平面的正值问题仍然是最难的问题。