# Partition Graph

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.

• I think you need to clarify your problem a bit more in order for anyone to be able to answer it. A partition of a graph is usually a partition $S = (V_1, V_2, \dots V_k)$ of the vertices of the graph. What does $G \backslash S$ mean? Are you saying $S$ is a set of nodes of the graph so that $|\{v \in S : uv \in E(G) \textrm{ for some } u \in V(G)\backslash S\}| \leq 2$? In which case, are you really just asking to find a 0-, 1-, or 2-separation of the graph? – Perry Elliott-Iverson Mar 24 '14 at 17:18
• Yes!!! Thanks! It is 3-connected graph problem. – sm2 Mar 25 '14 at 7:24

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

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

• Your algorithms solves bipartition problem with goal to balance nodes's weight, but I have another problem - key statement is only two nodes in partition may have connections with nodes outside partition – sm2 Mar 24 '14 at 13:35
• I found this link (sandia.gov/~bahendr/partitioning.html) on a quick Google search. It seems a fair amount of research has been done on the subject. I'd probably start with these research papers. – ml0105 Mar 24 '14 at 13:38