We study connectivity oracle under vertex failures, one of the most fundamental graph data structures with many applications. We provide a new deterministic connectivity oracle that handles update in O(k⁶) time and answers query in O(k) time, while using 2^O(k²) n + O(k²n α_c(n)) space and k^O(k²) n + O(m + k³ n log² n + k⁶n log n) preprocessing time. Although some previous works achieve k² ⋅ n^o(1) update time and O(k) query time [Long and Saranurak, 2022; Yaowei Long and Yunfan Wang, 2024], the update time is still n-dependent, while oracles that have n-independent update and query times [Michal Pilipczuk et al., 2022; Jan van den Brand and Thatchaphol Saranurak, 2019] cannot achieve optimal O(k) query time [Monika Henzinger et al., 2015] and often have Ω(n²) space and processing time. Our solution would be the first vertex-failure connectivity oracle that achieves O(k) query time with update time completely independent of n, while improving space usage and having competitive preprocessing time.

A k-fault-tolerant connectivity preserver of a directed n-vertex graph G is a subgraph H such that, for any edge set F ⊆ E(G) of size |F| ≤ k, the strongly connected components of G−F and H −F are the same. While some graphs require a preserver with Ω(2kn) edges [1], the best-known upper bound is $\tilde O\left( {k{2^k}{n^{2 - /k}}} \right)$ edges [2], leaving a significant gap of Ω(n1−1/k). In contrast, there is no gap in undirected graphs; the optimal bound of Θ(kn) has been well-established since the 90s [3].We nearly close the gap for directed graphs; we prove that there exists a k-fault-tolerant connectivity preserver with O(k4knlogn) edges, and we can construct one with O(8knlog5/2n) edges in poly(2kn) time.Our results also improve the state-of-the-art for a closely related object; a k-connectivity preserver of G is a subgraph H where, for all i ≤ k, the strongly i-connected components of G and H agree. By a known reduction, we obtain a k-connectivity preserver with O(k4knlogn) edges, improving the previous best bound of $\tilde O\left( {k{2^k}{n^{2 - 1/(k - 1)}}} \right)$ [2]. Therefore, for any constant k, our results are optimal to a logn factor for both problems.Lastly, we show that the exponential dependency on k is not inherent for k-connectivity preservers by presenting another construction with $O\left( {n{\text{ }}\sqrt {kn} } \right)$ edges.

Given a graph G = (V,E) (n = |V|, m = |E|) and two vertices s,t ∈ V, the f-fault replacement path (fFRP) problem computes for every set F of at most f edges, the distance from s to t when edges in F fail. A recent result shows that 2FRP in directed graphs can be solved in Õ(n³) time [Vassilevska Williams, Woldeghebriel, Xu 2022]. In this paper, we show a 3FRP algorithm in deterministic Õ(n³) time for undirected weighted graphs, which almost matches the size of the output. This implies that fFRP in undirected graphs can be solved in nearly optimal Õ(n^f) time for all f ≥ 3. To construct our 3FRP algorithm, we introduce an incremental distance sensitivity oracle (DSO) for undirected graphs with Õ(n²) worst-case update time, while preprocessing time, space, and query time are still Õ(n³), Õ(n²) and Õ(1), respectively, which match the static DSO [Bernstein and Karger 2009]. Here in a DSO, we can preprocess a graph so that the distance between any pair of vertices given any failed edge can be answered efficiently. From the recent result in [Peng and Rubinstein 2023], we can obtain an offline dynamic DSO from the incremental worst-case DSO, which makes the construction of our 3FRP algorithm more convenient. By the offline dynamic DSO, we can also construct a 2-fault single-source replacement path (2-fault SSRP) algorithm in Õ(n³) time, that is, from a given vertex s, we want to find the distance to any vertex t when any pair of edges fail. Thus the Õ(n³) time complexity for 2-fault SSRP is also nearly optimal. Now we know that in undirected graphs 1FRP can be solved in Õ(m) time [Nardelli, Proietti, Widmayer 2001], and 2FRP and 3FRP in undirected graphs can be solved in Õ(n³) time. In this paper, we also show that a truly subcubic algorithm for 2FRP in undirected weighted graphs does not exist under APSP hypothesis.

We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in m1+o(1) time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in m1+o(1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too.

In the last decades, Wireless Local Area Network (WLAN) has been emerging as one of the most prevailing networking architectures. It is expected that current WLAN technologies will further evolve to obtain much higher performance, more energy efficiency and more robustness. However, the WLAN is still prone to a variety of attacks regardless of the existence of data protection and security association mechanisms. They include but not limited to dictionary attacks against the pre-shared secret key of Wi-Fi Protected Access (WPA)/WPA2, the key reinstallation attack (KRACK) against the handshake procedure of WPA2, etc. Although a brand new WPA3 has been recently standardized by Wi-Fi Alliance to address new security threats, it needs a long time to upgrade currently used access points. Hence, there is a significant gap between security and deployment cost. To fill this gap, we design and implement an intellignet WLAN Early warning Platform (iWEP) to provide an early warning service for clients. Specifically, iWEP adopts intelligence algorithms, e.g., machine learning, to provide the capability of defeating existing popular attacks, including Wired Equivalent Privacy (WEP) secret cracking, WPA/WPA2 dictionary attack, Denial-of-Service and KRACK, by handling behaviour features that are extracted from the compromising procedures in real experimental environments. Moreover, iWEP uses edge computing technology to make a good tradeoff between system performance and WLAN security. Finally, we implement a prototype system of iWEP, and the real results demonstrate its effectiveness.