Minimum $k$k-Vertex Connected Graph Search

The <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-vertex connected (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-VC) subgraph, which remains connected with fewer than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-VCs, which are excessively large yet less cohesive in real applications. In this paper, we study the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">minimum <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-VC search (</i><italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><monospace>MinVC</monospace></i><italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">)</i> problem, seeking to find a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-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 <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Enum</monospace>, 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-VC model. To address this challenge, we propose an advanced method, called <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">VCtoB</monospace>, which divides the <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">MinVC</monospace> problem into several new sub-problems, called the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">fixed-size <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-VC</i> problems. Each of them can be solved efficiently by exploiting the hereditary property of the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$s$</tex-math></inline-formula>-bundle model. Finally, our empirical experiments on 139 real-world networks demonstrate that <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">VCtoB</monospace> achieves performance improvement of up to six orders of magnitude over the baseline.