Minimum $k$k-Vertex Connected Graph Search
Yang Liu, Hejiao Huang, Kaiqiang Yu, Shengxin Liu, Cheng Long · IEEE Transactions on Knowledge and Data Engineering · 2025
The$k$-vertex connected ($k$-VC) subgraph, which remains connected with fewer than$k$vertices being removed, is an essential structure in graph mining. It has found many applications, such as survivable network design and web search optimization. However, existing studies focus on mining maximal$k$-VCs, which are excessively large yet less cohesive in real applications. In this paper, we study theminimum$k$-VC search (MinVC)problem, seeking to find a$k$-VC with the minimum number of vertices. We formally prove that this problem is NP-hard and then propose two algorithms to obtain the exact solution. The basic method, calledEnum, follows a branch-and-bound framework with some pruning rules, which directly enumerates all possible vertex sets. Nonetheless, it suffers from the efficiency issues due to the non-hereditary property of the$k$-VC model. To address this challenge, we propose an advanced method, calledVCtoB, which divides theMinVCproblem into several new sub-problems, called thefixed-size$k$-VCproblems. Each of them can be solved efficiently by exploiting the hereditary property of the$s$-bundle model. Finally, our empirical experiments on 139 real-world networks demonstrate thatVCtoBachieves performance improvement of up to six orders of magnitude over the baseline.