Connected partitioning on spatial graphs with a bottleneck objective: formulation, exact calibration, and heuristic refinement

This work formalizes and evaluates a connected partitioning problem on spatial proximity graphs with a fixed number of clusters. The task is to divide vertices into k connected clusters, maximizing a bottleneck-cardinality utility in which each cluster contributes its cardinality multiplied by the smallest vertex attribute in the cluster. The evaluation combines an exact calibration baseline on microinstances, formulated as set partitioning over connected subsets, and a paired benchmark comparing a greedy constructor with a connectivity-preserving local refiner. In the n = 12 microinstances, the exact model solved all 15 tested seed-k combinations. In the main benchmark, with 30 paired runs on instances with 100 and 500 vertices, the refiner outperformed the constructor in all pairs, with an average gain of 81.59 and a significant one-sided Wilcoxon test (p = 9.31 × 10^-10). The results indicate systematic gains, at the cost of greater computational time.