2
$\begingroup$

Given a graph $G = (V, E)$, I need to determine:

  1. $k$, the graph connectivity.
  2. Which are those $k$ vertices to remove to make $G$ disconnected.

Questions

  • Which is the complexity of such problem?
  • Which are the fastest algorithms known?
  • What about if, additionally, I require that the resulting connected components have almost the same number of edges?

This question is an improvement of this question.

$\endgroup$
8
$\begingroup$

Both can be done efficiently. You can compute the connectivity of a graph by testing the connectivity of every pair using max-flow/min-cut and taking the smallest of the values gives you $k$ (see this on Menger's theorem) -- this gives you (1). Using the procedure above, you can test each vertex, one at a time, to see if its removal will decrease the connectivity. Once you find such a vertex, remove it and proceed -- this gives you (2).

$\endgroup$
  • 2
    $\begingroup$ I doubt this is the fastest though. $\endgroup$ – Suresh Venkat Mar 10 '11 at 20:19
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Minimum_cut gives references to faster algorithms. $\endgroup$ – Jukka Suomela Mar 10 '11 at 21:00
  • $\begingroup$ I'm sure it's not the fastest... $\endgroup$ – Lev Reyzin Mar 10 '11 at 21:20
  • 1
    $\begingroup$ For fast algorithms look at the paper of Henzinger, Rao and Gabow. dx.doi.org/10.1006/jagm.1999.1055 $\endgroup$ – Chandra Chekuri Mar 11 '11 at 21:12
5
$\begingroup$

What about if, additionally, I require that the resulting connected components have almost the same number of edges?

Then you are in trouble.

This is not exactly the same problem, but in general the following seems to hold for many variants of the theme: it is easy to find small cuts, but hard to find small balanced cuts (for any reasonable definitions of "small" and "balanced").

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.