SAGA: State-Aware Graph Analytics for Combinatorial Optimization on Dynamic Graphs

Listing Minimal Cores in Large Real-World Graphs

Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.

Fully dynamic strong connectivity and reachability in digraphs

. Computing strongly connected components (SCCs) and reachability in directed graphs is fundamental in compilers, static analysis, and many graph algorithms. While efficient offline algorithms are well known, maintaining this information dynamically under both edge insertions and deletions remains challenging. This paper presents a deterministic fully dynamic algorithm that simultaneously maintains SCCs and reachability in directed graphs. The approach combines a union–find structure for efficient merging of SCCs during edge insertions with localized recomputation of SCCs using Nuutila’s algorithm when deletions potentially split a component. Reachability information is maintained at the SCC level and propagated through the condensation DAG. For a current graph with n vertices and m edges, the resulting algorithm supports O (1) reachability queries while updates have worst-case complexity O ( m + n 2 ) due to reachability propagation. Although this does not improve the best known theoretical bounds for specialized dynamic algorithms, the method is simple, deterministic, and well suited to sparse graphs such as con-trol flow graphs (CFGs). Experimental evaluation on random graphs and real program CFGs shows that the algorithm significantly outperforms repeated offline recomputation in practical scenarios.

Efficient Simple Temporal Cycle Enumeration on Large Graphs with Lightweight Preprocessing

Temporal cycles are fundamental patterns in graphs, with important applications in finance, security, and neuroscience. In this work, we study the Simple Temporal Cycle Enumeration (STCE) problem, which aims to enumerate all simple cycles with strictly increasing timestamps within a given time window. However, existing methods, such as 2SCENT, suffer from redundant checks and expensive detection phase, making them inefficient for large-scale or dynamically evolving graphs. To overcome these challenges, we introduce a novel edge-centric framework that treats temporal edges as the core units of exploration. By computing edge offsets in linear time, we eliminate redundant temporal checks, and our constraint-based DFS avoids the expensive detection phase required by prior work. This design ensures polynomial delay and leads to substantial performance gains over existing approaches. Furthermore, we extend our framework to dynamic settings by introducing an efficient incremental update algorithm that selectively identifies affected paths only. Experiments show over an order-of-magnitude speedup on static graphs and up to six orders-of-magnitude improvement for dynamic updates, with most updates completing within 1 ms.

GECKO: Graph-Evolving aware ChecKpOinter for Intermittent Systems

Graph workloads increasingly rely on large, continuously evolving datasets, where SSD data placement and migration strongly influence query and update efficiency. Prior SSD based graph management schemes, including log based designs that follow a read modify write pattern and GraphSSD, target servers and PCs with stable power. When deployed on intermittently powered systems, these power unaware designs often scatter frequently updated hub node edges across many flash pages, which increases over read and triggers excessive flash I/O. The resulting energy overhead is further amplified after each power recovery because the system must reload graph data from NAND into DRAM, repeatedly paying for unnecessary reads and reducing the number of graph queries completed per charge cycle. We propose Graph Evolving aware ChecKpOinter (GECKO), which leverages graph evolution awareness to improve hub edge locality and applies power aware I/O coordination to reduce redundant flash accesses under intermittent power. Across evolving graph updates and queries, GECKO significantly lowers flash I/O, enabling better energy efficiency on energy constrained intermittent systems.

Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers

We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pm\epsilon)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_{\epsilon}(n^2)$ and worst-case query time $\widetilde{O}_{\epsilon}(1)$. Thus, for dense graphs where $m = \Omega(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/\epsilon)$ epochs such that every graph within an epoch is a $(1\pm O(\epsilon))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.

Worst-Case Optimal BGPs on Temporal Graphs