  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{\Delta}{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.
