# Weighted vertex-connectivity; global min vertex-cut

I am interested in the following problem:

Input: a connected undirected graph $G=(V,E)$; a positive weight for each vertex.

Output: a minimum weight subset of $V$ whose removal disconnects $G$.

When each vertex has the same weight this is equivalent to determining the vertex-connectivity. Intuitively, it is the vertex version of the global minimum cut problem.

I can think of an $O(mn^3)$ algorithm that solves $O(n^2)$ minimum $s$-$t$ cut problems, but I expect that there should be a faster approach. Does this problem have a name? What is the fastest known algorithm?

• Harold N. Gabow: Using expander graphs to find vertex connectivity. J. ACM 53(5): 800-844 (2006) Monika Rauch Henzinger, Satish Rao, Harold N. Gabow: Computing Vertex Connectivity: New Bounds from Old Techniques. J. Algorithms 34(2): 222-250 (2000) – Chandra Chekuri May 29 '13 at 22:35
• so, given several/lots of s-t cut problems, you're wondering if there's a faster way to $\hspace{.58 in}$ solve all of them than solving them independently? $\:$ – user6973 May 30 '13 at 2:35
• @RickyDemer No. See the "input" and "output." One way to solve this problem is to solve several s-t cut problems, but Chandra's links show this isn't the fastest way. – Austin Buchanan May 30 '13 at 3:15
• @ChandraChekuri I'd be happy to accept your comment as an answer – Austin Buchanan Dec 8 '13 at 4:04