Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
复制标题
在一般图中维护 EDCS：更简单、密度敏感且具有最坏情况时间范围
DOI：
10.1137/1.9781611977066.2
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Amitai Uzrad
中科院分区：
文献类型：
--
作者：
F. Grandoni;Chris Schwiegelshohn;Shay Solomon;Amitai Uzrad
在他们具有突破性的ICALP'15论文中，伯恩斯坦（Bernstein）和斯坦（Stein）提出了一种算法，用于在完全动态的**二分图**中维护一个$(3/2 + \epsilon)$ - 近似最大匹配，其**最坏情况**下的更新时间为$O_\epsilon(m^{1/4})$；我们使用$O_\epsilon$符号来隐藏对$\epsilon$的依赖。他们的主要技术贡献在于提出了一种新型的有界度子图，他们将其命名为**边度约束子图（EDCS）**，该子图包含一个较大的匹配——其大小比整个图的最大匹配大小最多小$(3/2 + \epsilon)$倍。他们证明了EDCS可以在最坏情况更新时间为$O_\epsilon(m^{1/4})$的情况下进行维护，并且他们的主要结果是一个直接的推论。在他们后续的SODA'16论文中，伯恩斯坦和斯坦将他们的结果推广到一般图，实现了相同的$O_\epsilon(m^{1/4})$更新时间，尽管是摊销界限而非最坏情况界限。到目前为止，对于**任何**优于2 - 近似匹配的**确定性**最坏情况更新时间界限是$O(\sqrt{m})$[尼曼（Neiman）和所罗门（Solomon），STOC'13]，[古普塔（Gupta）和彭（Peng），FOCS'13]；允许随机化（针对无感知对手），对于略小于2的近似，可以实现好得多（仍然是多项式的）更新时间[贝赫内扎德（Behnezhad）、拉茨基（Lacki）和米罗科尼（Mirrokni），SODA'20]。在这项工作中，我们\(^{\text{脚注：站在巨人肩上的侏儒}}\)简化了伯恩斯坦和斯坦针对二分图的方法，这使我们能够将其推广到一般图，同时在**最坏情况**更新时间上保持相同的$O_\epsilon(m^{1/4})$界限。此外，我们的方法是**密度敏感的**：如果动态图的**树度**在任何时候都被$\alpha$所限制，那么算法的最坏情况更新时间是$O_\epsilon(\sqrt{\alpha})$。
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an algorithm for maintaining a $(3/2+\epsilon)$-approximate maximum matching in fully dynamic {\em bipartite} graphs with a {\em worst-case} update time of $O_\epsilon(m^{1/4})$; we use the $O_\epsilon$ notation to suppress the $\epsilon$-dependence. Their main technical contribution was in presenting a new type of bounded-degree subgraph, which they named an {\em edge degree constrained subgraph (EDCS)}, which contains a large matching -- of size that is smaller than the maximum matching size of the entire graph by at most a factor of $3/2+\epsilon$. They demonstrate that the EDCS can be maintained with a worst-case update time of $O_\epsilon(m^{1/4})$, and their main result follows as a direct corollary. In their followup SODA'16 paper, Bernstein and Stein generalized their result for general graphs, achieving the same update time of $O_\epsilon(m^{1/4})$, albeit with an amortized rather than worst-case bound. To date, the best {\em deterministic} worst-case update time bound for {\em any} better-than-2 approximate matching is $O(\sqrt{m})$ [Neiman and Solomon, STOC'13], [Gupta and Peng, FOCS'13]; allowing randomization (against an oblivious adversary) one can achieve a much better (still polynomial) update time for approximation slightly below 2 [Behnezhad, Lacki and Mirrokni, SODA'20]. In this work we\footnote{\em quasi nanos, gigantium humeris insidentes} simplify the approach of Bernstein and Stein for bipartite graphs, which allows us to generalize it for general graphs while maintaining the same bound of $O_\epsilon(m^{1/4})$ on the {\em worst-case} update time. Moreover, our approach is {\em density-sensitive}: If the {\em arboricity} of the dynamic graph is bounded by $\alpha$ at all times, then the worst-case update time of the algorithm is $O_\epsilon(\sqrt{\alpha})$.
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Bhattacharya S
通讯作者：
Bhattacharya S
核心集满足 EDCS：海量图上的匹配和顶点覆盖算法
DOI：
--
发表时间：
2019
期刊：
SODA 2019
影响因子：
--
作者：
Assadi, S.
Batenai
通讯作者：
Assadi, S.
Batenai