---
title: "A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem"
authors:
  - "Rui Sun"
  - "Xinyu Wang"
  - "Yiyuan Wang"
  - "Jiangnan Li"
  - "Yi Zhou"
doi: "10.24963/ijcai.2025/996"
url: "https://ijcai.org/proceedings/2025/996"
pdf: "https://ijcai.org/proceedings/2025/0996.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8956-8965"
track: "Main Track"
keywords:
  - "Search: S: Heuristic search"
  - "Search: S: Local search"
---

# A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem

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

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 8956-8965. DOI: [10.24963/ijcai.2025/996](https://doi.org/10.24963/ijcai.2025/996)

## 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.