Given a graph $G = (V, E)$, I need to determine:
- $k$, the graph connectivity.
- Which are those $k$ vertices to remove to make $G$ disconnected.
- 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.