论文标题
一般图中的减少匹配
Decremental Matching in General Graphs
论文作者
论文摘要
我们考虑在动态图$ g $中维持近似最大积分匹配的问题，而对手则更改图表的边缘。目标是维持$（1+ε）$ - 常数$ε> 0 $的大约最大匹配，同时最小化更新时间。在允许边缘插入和删除的完全动态设置中，Gupta和Peng（请参阅\ cite {gp13}）给出了一个算法，以解决此问题的算法，更新时间为$ O（\ sqrt {M} {M}/ε^2）$。 很难克服$o_ε（\ sqrt {m}）$屏障的动机（请参阅Henzinger，Krinninger，Nanongkai和Saranurak [HKNS15]）； Kopelowitz，Pettie和Porat [Kpp16]），我们在\ emph {dissemental}模型中研究了此问题，其中只允许对手删除边缘。最近，Bernstein，Probst-Gutenberg和Saranurak（参见[BPT20]）给出了$O_ε（1）$更新此问题的$o_ε（1）$更新时间减少算法。但是，击败$ o（\ sqrt {m}）$更新时间仍然是\ emph {常规图}的打开问题。 在本文中，我们通过给出$O_ε（1）$更新时间算法，该算法维持$（1+ε）$ - 在对抗删除下的近似最大积分匹配。我们的算法是随机的，但与自适应对手有关。以及Grandoni，Leonardi，Sankowski，Schwiegelshohn和Solomon [GLSSSS19]的作品，他们给出了$ o_is（1）$更新时间算法的一般图中的一般图中的\ emph {incoremental}（insertion-onerly）模型的型号，我们的结果基本上完成了部分匹配图片的结果。
We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph $G$, while the adversary makes changes to the edges of the graph. The goal is to maintain a $(1+ε)$-approximate maximum matching for constant $ε>0$, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see \cite{GP13}) gave an algorithm for this problem with an update time of $O(\sqrt{m}/ε^2)$. Motivated by the fact that the $O_ε(\sqrt{m})$ barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [HKNS15]); Kopelowitz, Pettie, and Porat [KPP16]), we study this problem in the \emph{decremental} model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [BPT20]) gave an $O_ε(1)$ update time decremental algorithm for this problem in \emph{bipartite graphs}. However, beating $O(\sqrt{m})$ update time remained an open problem for \emph{general graphs}. In this paper, we bridge the gap between bipartite and general graphs, by giving an $O_ε(1)$ update time algorithm that maintains a $(1+ε)$-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [GLSSS19] who give an $O_ε(1)$ update time algorithm for general graphs in the \emph{incremental} (insertion-only) model, our result essentially completes the picture for partially dynamic matching.
