I need to find partition (S) (with more then 2 nodes) of a non-oriented graph (G), that containes no more than two nodes connected with the rest of graph (G \ S)
I could invent an algorithm of brute force of pairs of nodes, but I need a more optimal algorithm.
On
This problem is NP-Hard. So the best you'll get are approximations or inefficient algorithms.
A couple algorithms are: Kernighan-Lin: http://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm
Fiduccia-Mattheyses: http://en.wikipedia.org/wiki/Fiduccia-Mattheyses_algorithm
Assuming you're looking for 2-separations in a 2-connected graph, the following paper of Hopcroft and Tarjan could be useful. They find the triconnected components of a graph in $O(v+e)$ time:
http://ecommons.cornell.edu/bitstream/1813/6037/1/74-197.pdf
See also: http://en.wikipedia.org/wiki/SPQR_tree