  There has recently been much progress on exact algorithms for the
(un)weighted graph (bi)partitioning problem using branch-and-bound and related
methods. In this note we present and improve an easily computable, purely
combinatorial lower bound for the weighted bipartitioning problem. The bound is
computable in $O(n\log n+m)$ time steps for weighted graphs with $n$ vertices
and $m$ edges. In the branch-and-bound setting, the bound for each new
subproblem can be updated in $O(n+(m/n)\log n)$ time steps amortized over a
series of $n$ branching steps; a rarely triggered tightening of the bound
requires search on the graph of unassigned vertices and can take from $O(n+m)$
to $O(nm+n^2\log n)$ steps depending on implementation and possible bound
quality. Representing a subproblem uses $O(n)$ space. Although the bound is
weak, we believe that it can be advantageous in a parallel setting to be able
to generate many subproblems fast, possibly out-weighting the advantages of
tighter, but much more expensive (algebraic, spectral, flow) lower bounds.
  We use a recent priority task-scheduling framework for giving a parallel
implementation, and show the relative improvements in bound quality and
solution speed by the different contributions of the lower bound. A detailed
comparison with standardized input graphs to other lower bounds and frameworks
is pending. Detailed investigations of branching and subproblem selection rules
are likewise not the focus here, but various options are discussed.
