论文标题
在大图上的动态近似最大独立集
Dynamic Approximate Maximum Independent Set on Massive Graphs
论文作者
论文摘要
计算最大独立集（MAXIS）是图理论中的基本NP-硬性问题，该问题在广泛的领域中具有重要的应用。由于随着时间的流逝，许多应用程序中的图形经常发生变化，因此在过去几年中，维持MAXIS上的Maxis的问题引起了人们的关注。由于维持准确的超长的棘手性，本文旨在开发有效的算法，从而可以在理论上保持准确的保证，从而维持近似值。特别是，我们提出了一个框架，该框架维持$（\fracδ{2} + 1）$ - 在动态图上近似Maxis，并证明它在许多现实世界网络中达到了常数近似值。据我们所知，这是动态Maxis问题的第一个非平底近似性结果。在框架之后，我们实现了一种有效的线性时间动态算法和更有效的动态算法，具有接近线性的预期时间复杂性。我们对真实和合成图的详尽实验证明了所提出算法的有效性和效率，尤其是当图高度动态时。
Computing a maximum independent set (MaxIS) is a fundamental NP-hard problem in graph theory, which has important applications in a wide spectrum of fields. Since graphs in many applications are changing frequently over time, the problem of maintaining a MaxIS over dynamic graphs has attracted increasing attention over the past few years. Due to the intractability of maintaining an exact MaxIS, this paper aims to develop efficient algorithms that can maintain an approximate MaxIS with an accuracy guarantee theoretically. In particular, we propose a framework that maintains a $(\fracΔ{2} + 1)$-approximate MaxIS over dynamic graphs and prove that it achieves a constant approximation ratio in many real-world networks. To the best of our knowledge, this is the first non-trivial approximability result for the dynamic MaxIS problem. Following the framework, we implement an efficient linear-time dynamic algorithm and a more effective dynamic algorithm with near-linear expected time complexity. Our thorough experiments over real and synthetic graphs demonstrate the effectiveness and efficiency of the proposed algorithms, especially when the graph is highly dynamic.
