  The Balanced Connected Subgraph problem (BCS) was recently introduced by
Bhore et al. (CALDAM 2019). In this problem, we are given a graph $G$ whose
vertices are colored by red or blue. The goal is to find a maximum connected
subgraph of $G$ having the same number of blue vertices and red vertices. They
showed that this problem is NP-hard even on planar graphs, bipartite graphs,
and chordal graphs. They also gave some positive results: BCS can be solved in
$O(n^3)$ time for trees and $O(n + m)$ time for split graphs and properly
colored bipartite graphs, where $n$ is the number of vertices and $m$ is the
number of edges.
  In this paper, we show that BCS can be solved in $O(n^2)$ time for trees and
$O(n^3)$ time for interval graphs. The former result can be extended to bounded
treewidth graphs. We also consider a weighted version of BCS (WBCS). We prove
that this variant is weakly NP-hard even on star graphs and strongly NP-hard
even on split graphs and properly colored bipartite graphs, whereas the
unweighted counterpart is tractable on those graph classes. Finally, we
consider an exact exponential-time algorithm for general graphs. We show that
BCS can be solved in $2^{n/2}n^{O(1)}$ time. This algorithm is based on a
variant of Dreyfus-Wagner algorithm for the Steiner tree problem.
