Partition a graph into 2 connected subgraphs I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are $m$ vertices in $G$, subgraphs $G_{1}$ and $G_{2}$ should have 

\begin{equation}
|V_{1}| + |V_{2}| = |V|
\end{equation}
\begin{equation}
(|V_{1}| - |V|/2)^{2} \leq \epsilon^{2}, (|V_{2}| - |V|/2)^{2} \leq \epsilon^{2}
\end{equation}

and $V_{1}$ and $V_{2}$ should be disjoint.

Anyone know a quick way to compute if this exists and what the partition should be? I know that partitioning in general is NP-hard but I didn't know if it was for this special case.
The problem you asked is the unweighted version of the Balance Connected 2-Partition ($BCP_2$).

For unweighted case, any 2-connected graph can be partitioned into two connected subgraphs whose numbers of vertices differ by at most one. A simple algorithm uses st-numbering. For any 2-connected graph, we can label the vertices by $[1...n]$ such that any vertex has simultaneously a neighbor with smaller label and a neighbor with larger label. Let $V_1=\{1...n/2\}$ and $V_2=V-V_1$. It can be easily shown that both $V_1$ and $V_2$ induce connected subgraphs.

However, when there are cut vertices, the problem is NP-hard because it is equivalent to the weighted $BCP_2$. The transformation is as follows. Let $v$ be a cut vertex and $H$ be the maximum connected component in $G-v$. We shrink all components other than $H$ into $v$ and the weight of $v$ is given by the weight of the vertices combined in $v$. Repeat this process and we can obtain a weighted 2-connected graph.

It can be easily realized that there exists a graph such that the minimum part contains only $n/3$ vertices in any 2-partition.

For $BCP_2$, the currently best approximation algorithm is due to Chlebikova (I hope that it is not out of date): 

Approximating the maximally balanced connected partition problem in graphs, Information Processing Letters, 60:225--230, 1996. The approximation ratio is 4/3. For some special graphs, there are better results. For example, FPTAS for interval graphs and 5/4-approximation for grid graphs (further improved to 7/6).