An Effective Branch-and-Bound Algorithm with New Bounding Methods for
  the Maximum $s$-Bundle Problem
Jinghui Xue Jiongzhi Zheng Mingming Jin Kun He
The Maximum s-Bundle Problem (MBP) addresses the task of identifying a
maximum s-bundle in a given graph. A graph G=(V, E) is called an s-bundle if
its vertex connectivity is at least |V|-s, where the vertex connectivity equals
the minimum number of vertices whose deletion yields a disconnected or trivial
graph. MBP is NP-hard and holds relevance in numerous realworld scenarios
emphasizing the vertex connectivity. Exact algorithms for MBP mainly follow the
branch-and-bound (BnB) framework, whose performance heavily depends on the
quality of the upper bound on the cardinality of a maximum s-bundle and the
initial lower bound with graph reduction. In this work, we introduce a novel
Partition-based Upper Bound (PUB) that leverages the graph partitioning
technique to achieve a tighter upper bound compared to existing ones. To
increase the lower bound, we propose to do short random walks on a clique to
generate larger initial solutions. Then, we propose a new BnB algorithm that
uses the initial lower bound and PUB in preprocessing for graph reduction, and
uses PUB in the BnB search process for branch pruning. Extensive experiments
with diverse s values demonstrate the significant progress of our algorithm
over state-of-the-art BnB MBP algorithms. Moreover, our initial lower bound can
also be generalized to other relaxation clique problems.