# Recent Advances in Efficient Dynamic Graph Processing
## 3 Computational Complexity Model  
In the literature, asymptotic worst-case analysis serves as a standard method for assessing algorithm complexity, representing computational cost as a function of input size. In the case of dynamic graph algorithms, if runtime is measured as a function of input size, many such algorithms exhibit worst-case complexity that is often no more efficient than simply recomputing the solution from scratch. Clearly, assessing the computational complexity of dynamic graph algorithms in this way provides little meaningful insight. As a result, the literature examines various computational complexity frameworks, such as _boundedness_, _relative boundedness_, and _semi-boundedness_. **Definition 1** (Boundedness [128]). : _A dynamic algorithm is considered bounded if its cost is a polynomial in \(|\mathsf{CHANGED}|\) and \(|Q|\)._  
The concept of _boundedness_ is first introduced in [129] to address limitations of worst-case analysis, and later adapted for graph problems in [128]. In [128], the authors propose \(|\mathsf{CHANGED}|\) as an adaptive metric for quantifying input and output modifications. For a given query class \(\mathcal{Q}\), when applying update \(\Delta(G)\) to graph \(G\) and computing \(Q(G\oplus\Delta(G))\), the output changes \(\Delta(O)\) must satisfy \(Q(G\oplus\Delta(G))=Q(G)\oplus\Delta(O)\). The study [128] establishes two key terms: MODIFIED captures graph input change \(\Delta(G)\), while AFFECTED describes query output change \(\Delta(O)\). The combined change CHANGED is defined as MODIFIED\(\cup\)AFFECTED to measure total system changes. \(|\mathsf{CHANGED}|\) measures the size of CHANGED. Based on \(|\mathsf{CHANGED}|\), a dynamic algorithm exhibits _bounded_ if the time taken for the update is a function of the parameter of \(|\mathsf{CHANGED}|\). In contrast, it demonstrates _unbounded_ if the computational time grows without bound even when \(|\mathsf{CHANGED}|\) remains constant. **Definition 2** (Relative Boundedness [130]). : _A dynamic algorithm is called bounded relative if its cost can be expressed as a polynomial function in the sizes of \(|\mathsf{AFF}|\), \(|\Delta(G)|\), and \(|Q|\)._  
Building upon the concept of boundedness, Ref. [130] puts forward two alternative approaches to assess computational complexity: _localizable computations_ and _relative boundedness_. Ref. [130] proposes that the dynamic problem for \(Q\) is deemed _localizable_ if there exists an incremental algorithm \(\mathcal{T}_{\Delta}\) such that for \(Q\in\mathcal{Q}\), \(G\) and \(\Delta G\), its computational cost is solely determined by \(|Q|\) and the \(d_{Q}\)-neighbors of nodes in \(\Delta G\), where \(d_{Q}\) is exclusively dependent on \(|Q|\) only. Consider a query \(Q\in\mathcal{Q}\) and a graph \(G\), Ref. [130] defines \(G_{\mathcal{T},Q}\) as part of the data of \(G\) examined by algorithm \(\mathcal{T}\) when evaluating \(Q(G)\). Given updates \(\Delta G\) to \(G\), AFF measures the variation between the inspected data before and after updates (i.e., \((G\oplus\Delta G)_{(\mathcal{T},Q)}\) and \(G_{(\mathcal{T},Q)}\)). A dynamic algorithm \(\mathcal{T}_{\Delta}\) for \(\mathcal{Q}\) is _bounded relative_ to \(\mathcal{T}\) if its execution cost scales polynomially with \(|\mathsf{AFF}|\), \(|\Delta G|\), and \(|Q|\). **Definition 3** (**Semi-Boundedness**[131]). : _A dynamic algorithm is said to be semi-bounded if: (a) its computational cost is a polynomial in \(|\mathsf{AFF}^{\forall}|\), \(|\Delta G|\), and \(|Q|\); and (b) the size of the auxiliary structure is bounded by a polynomial function of \(|G|\)._  
The metric \(|\mathsf{CHANGED}|\), while accurately reflecting the inherent update costs in dynamic graph problems, imposes such stringent conditions that most practical dynamic graph algorithms cannot achieve bounded complexity under this framework. Consequently, Ref. [131] proposes a more relaxed metric centered on the concept of affected area \(\mathsf{AFF}^{\forall}\).