A Clustering Based Iterated Hybrid Search For Vertex Bisection Problem

Given a simple and undirected graph G=(V,E),graph partitioning problem aims to find a partition of its vertices optimizing a particular objective function.The vertex bisection problem is an important branch of graph partitioning problem.It aims to split the vertices into two sets B and B' of approximately equal cardinalities and minimize the number of vertices in B which have at least one connected vertex with B'.The vertex bisection problem is usually NP-hard,but in some special data structures,such as hypercubes and trees,the vertex bisection problem can be solved in polynomial time.As an important branch of graph partitioning problem,the vertex bisection problem has a wide range of applications,such as the design of very-large-scale-integration circuits,network communication,image processing,task scheduling in multi-processor systems,etc.The study of vertex bisection problem has important theoretical value and practical significance.This paper proposes a clustering based iterated hybrid search algorithm CIHS to solve the vertex bisection problem.First,this paper proposes a strategy for vertex bisection problem to measure the similarity between vertices,and uses the similarity matrix of the graph to perform a preprocessing process based on a hierarchical clustering.Secondly,this paper proposes a cluster-constrained move operator in local search.During this operation,the vertices in some clusters will not move.Finally,this paper proposes a perturbation program based on clustering.During the perturbation,the state of clusters will be changed to diversify the search and jump out of the local optimal.According to the comparison of the results of CIHS and the state-of-the-art,the search algorithm combined with clustering can solve the vertex bisection problem more efficiently,and on larger-scale graphs,the improvement of the search algorithm by clustering is more obvious.