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?

  • 4
    $\begingroup$ 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) $\endgroup$ May 29 '13 at 22:35
  • $\begingroup$ 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? $\:$ $\endgroup$
    – user6973
    May 30 '13 at 2:35
  • $\begingroup$ @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. $\endgroup$ May 30 '13 at 3:15
  • $\begingroup$ @ChandraChekuri I'd be happy to accept your comment as an answer $\endgroup$ Dec 8 '13 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.