Minimum k-Vertex Connected Graph Search

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 the minimum 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, called Enum, 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, called VCtoB, which divides the MinVC problem into several new sub-problems, called the fixed-size k-VC problems. 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 that VCtoB achieves performance improvement of up to six orders of magnitude over the baseline.