# 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) 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. May 30 '13 at 3:15
• @ChandraChekuri I'd be happy to accept your comment as an answer Dec 8 '13 at 4:04