  Graph partitioning (GP) and vertex connectivity have traditionally been two
distinct fields of study. This paper introduces the highly connected graph
partitioning (HCGP) problem, which partitions a graph into compact, size
balanced, and $Q$-(vertex) connected parts for any $Q\geq 1$. This problem is
valuable in applications that seek cohesion and fault-tolerance within their
parts, such as community detection in social networks and resiliency-focused
partitioning of power networks. Existing research in this fundamental
interconnection primarily focuses on providing theoretical existence guarantees
of highly connected partitions for a limited set of dense graphs, and do not
include canonical GP considerations such as size balance and compactness. This
paper's key contribution is providing a general modeling and algorithmic
approach for HCGP, inspired by recent work in the political districting
problem, a special case of HCGP with $Q=1$. This approach models
$Q$-connectivity constraints as mixed integer programs for any $Q\geq 1$ and
provides an efficient branch-and-cut method to solve HCGP. When solution time
is a priority over optimality, this paper provides a heuristic method
specifically designed for HCGP with $Q=2$. A computational analysis evaluates
these methods using a test bed of instances from various real-world graphs. In
this analysis, the branch-and-cut method finds an optimal solution within one
hour in $82.8\%$ of the instances solved. For $Q=2$, small and sparse instances
are challenging for the heuristic, whereas large and sparse instances are
challenging for the exact method. Furthermore, this study quantifies the
computational cost of ensuring higher connectivity using the branch-and-cut
approach, compared to a baseline of ensuring $1$-connectivity. Overall, this
work serves as an effective tool to partition a graph into resilient and
cohesive parts.
