<p>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 <a href="http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29#Computational_aspects" rel="nofollow">this</a> 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).</p>

CC BY-SA 2.5
2011-03-10T20:19:30.003Z
I doubt this is the fastest though.
Suresh Venkat
CC BY-SA 2.5
2011-03-10T21:00:33.643Z
http://en.wikipedia.org/wiki/Minimum_cut gives references to faster algorithms.
Jukka Suomela
CC BY-SA 2.5
2011-03-10T21:20:28.373Z
I'm sure it's not the fastest...
Lev Reyzin
CC BY-SA 2.5
2011-03-11T21:12:24.527Z
For fast algorithms look at the paper of Henzinger, Rao and Gabow. dx.doi.org/10.1006/jagm.1999.1055
Chandra Chekuri
CC BY-SA 2.5
2011-03-10T19:00:24.643Z
2011-03-10T19:00:24.643Z
Lev Reyzin
<blockquote>
  <p>What about if, additionally, I require that the resulting connected components have almost the same number of edges?</p>
</blockquote>

<p>Then you are <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node95.html" rel="nofollow">in trouble</a>.</p>

<p>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").</p>

CC BY-SA 2.5
2011-03-10T19:50:43.760Z
2011-03-10T19:50:43.760Z
Jukka Suomela
<p>Given a graph $G = (V, E)$, I need to determine:</p>

<ol>
<li>$k$, the graph connectivity.</li>
<li>Which are those $k$ vertices to remove to make $G$ disconnected.</li>
</ol>

<blockquote>
  <p><strong>Questions</strong>  </p>
  
  <ul><li>Which is the complexity of such problem?</li>
  <li>Which are the fastest algorithms known?</li>
  <li>What about if, additionally, I require that the resulting connected components have almost the same number of edges?</li></ul>  
</blockquote>

<p>This question is an improvement of <a href="https://cstheory.stackexchange.com/questions/1541/connected-components-of-k-cnf-formulas">this</a> question.</p>

<ds.algorithms><reference-request><graph-algorithms>
Graph Connectivity
Giorgio Camerani
# Graph Connectivity

(Asked by: username_0 on 2011-03-10)

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](https://cstheory.stackexchange.com/questions/1541/connected-components-of-k-cnf-formulas) question.

**Tags:** ds.algorithms, reference-request, graph-algorithms

---

## 2 answers

### Answer by username_1 on 2011-03-10. Score: 8 | Accepted answer

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](http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29#Computational_aspects) 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).

> **Comments:**
> **username_2**: I doubt this is the fastest though.  
> **username_3**: http://en.wikipedia.org/wiki/Minimum_cut gives references to faster algorithms.  
> **username_1**: I'm sure it's not the fastest...  
> **username_4**: For fast algorithms look at the paper of Henzinger, Rao and Gabow. dx.doi.org/10.1006/jagm.1999.1055  

---

### Answer by username_3 on 2011-03-10. Score: 5

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

Then you are [in trouble](http://www.nada.kth.se/~viggo/wwwcompendium/node95.html).

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").


---

