Highly Connected Graph Partitioning: Exact Formulation and Solution Methods
提出了高连通图划分问题，要求把图分成规模均衡且Q连通的紧凑部分，并给出了混合整数规划与分支切割求解方法，还针对Q=2设计了启发式。对社区发现、电力网络韧性等应用有帮助。
Graph partitioning (GP) and vertex connectivity have traditionally been two distinct fields of study. This paper bridges this gap by introducing the highly connected graph partitioning (HCGP) problem, which partitions a graph into compact, size balanced, and Q-(vertex) connected parts for any Q≥1. This problem is valuable in applications that seek cohesion and fault-tolerance within their parts, such as community detection in social networks and resilient partitioning of power networks. Existing research in this fundamental interconnection focuses on 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≥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 customized for Q=2. A computational analysis evaluates these methods using a test bed of instances from various real-world graphs. The branch-and-cut method finds an optimal solution within one hour in 82.8% of the instances solved. This study also quantifies the computational cost of ensuring higher connectivity using the branch-and-cut approach, compared to a baseline of ensuring 1-connectivity. This paper serves effective tools to partition a graph into resilient and cohesive parts.