A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem

Sun, Rui; Wang, Xinyu; Wang, Yiyuan; Li, Jiangnan; Zhou, Yi

doi:10.24963/ijcai.2025/996

A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem

Rui Sun, Xinyu Wang, Yiyuan Wang, Jiangnan Li, Yi Zhou

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8956-8965.

https://doi.org/10.24963/ijcai.2025/996

Keywords

Search: S: Heuristic search
Search: S: Local search

Abstract

The vertex bisection minimization problem (VBMP) is a fundamental graph partitioning problem with numerous real-world applications. In this study, we propose a (k, l, S)-cluster guided local search algorithm to address this challenge.

First, we propose a novel (k,l,S)-cluster enumeration procedure, which is based on two key concepts: the (k, l, S)-cluster and the local cluster core. The (k, l, S)-cluster limits both the connectivity and distinct boundaries of a given vertex set, and the local cluster core represents the most cohesive substructure within a (k, l, S)-cluster. Building up on the above (k, l, S)-cluster enumeration procedure, we present a novel (k, l, S)-cluster guided perturbation mechanism designed to escape from local optima.

Next, we propose a two-manner local search procedure that employs two distinct search models to explore the neighboring search space efficiently. Experimental results demonstrate that the proposed algorithm performs best on nearly all instances.

Rui Sun, Xinyu Wang, Yiyuan Wang, Jiangnan Li, and Yi Zhou. 2025. A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8956–8965. https://doi.org/10.24963/ijcai.2025/996

@inproceedings{ijcai2025p996,
  title     = {A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem},
  author    = {Sun, Rui and Wang, Xinyu and Wang, Yiyuan and Li, Jiangnan and Zhou, Yi},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {8956--8965},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/996},
  url       = {https://doi.org/10.24963/ijcai.2025/996},
}

TY  - CPAPER
TI  - A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem
AU  - Sun, Rui
AU  - Wang, Xinyu
AU  - Wang, Yiyuan
AU  - Li, Jiangnan
AU  - Zhou, Yi
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 8956
EP  - 8965
DO  - 10.24963/ijcai.2025/996
UR  - https://doi.org/10.24963/ijcai.2025/996
ER  -