<p>I am interested in the following problem:</p>
<blockquote>
<p><strong>Input</strong>: a connected undirected graph <span class="math-container">$G=(V,E)$</span>; a positive weight for each vertex.</p>
<p><strong>Output</strong>: a minimum weight subset of <span class="math-container">$V$</span> whose removal disconnects <span class="math-container">$G$</span>.</p>
</blockquote>
<p>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.</p>
<p>I can think of an <span class="math-container">$O(mn^3)$</span> algorithm that solves <span class="math-container">$O(n^2)$</span> minimum <span class="math-container">$s$</span>-<span class="math-container">$t$</span> cut problems, but I expect that there should be a faster approach. Does this problem have a name? What is the fastest known algorithm?</p>

CC BY-SA 3.0
2013-12-08T04:04:08.150Z
@ChandraChekuri I'd be happy to accept your comment as an answer
Austin Buchanan
CC BY-SA 3.0
2013-05-29T22:35:28.947Z
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
CC BY-SA 3.0
2013-05-30T03:15:38.673Z
@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
<graph-algorithms><max-flow-min-cut>
Weighted vertex-connectivity; global min vertex-cut
Austin Buchanan
# Weighted vertex-connectivity; global min vertex-cut

(Asked by: username_0 on 2013-05-29)

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?

**Tags:** graph-algorithms, max-flow-min-cut
> **Comments:**
> **username_1**: 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)  
> **username_0**: @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.  
> **username_0**: @ChandraChekuri I'd be happy to accept your comment as an answer  

---

## 0 answers

