k-way graph partitioning is an NP-complete problem, which is applied to various tasks such as route planning, image segmentation, community detection, and high-performance computing. The approximate methods constitute a useful solution for these types of problems. Thus, many research studies have focused on developing meta-heuristic algorithms to tackle the graph partitioning problem. Local search is one of the earliest methods that has been applied efficiently to this type of problem. Recent studies have explored various types of local search methods and have improved them such that they can be used with the partitioning process. Moreover, local search methods are widely integrated with population-based approaches, to provide the best diversification and intensification for the problem space. This study emphasizes the local search approaches, as well as their combination with other graph partitioning approaches. At present, none of the surveys in the literature has focused on this class of state of the art approaches in much detail. In this study, the vital parts of these approaches including neighborhood structure, acceptance criterion, and the ways of combining them with other approaches, are highlighted. Additionally, we provide an experimental comparison that shows the variance in the performance of the reviewed methods. Hence, this study clarifies these methods to show their advantages and limitations for the targeted problem, and thus can aid in the direction of research flow towards the area of graph partitioning.

1. [1] J. M. Pujol, V. Erramilli, and P. Rodriguez, “Divide and conquer: Partitioning online social networks,” arXiv preprint, arXiv:0905.4918, 2009.
2. [2] A. Słowik and M. Białko, “Partitioning of VLSI circuits on subcircuits with minimal number of connections using evolutionary algorithm,” Int. Conf. on Artificial Intelligence and Soft Computing, pp. 470-478, 2006.
3. [3] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel hypergraph partitioning: applications in VLSI domain,” IEEE Trans. on Very Large Scale Integration (VLSI) Systems, Vol.7, No.1, pp. 69-79, 1999.
4. [4] B. Hendrickson and R. Leland, “An improved spectral graph partitioning algorithm for mapping parallel computations,” SIAM J. on Scientific Computing, Vol.16, No.2, pp 452-469, 1995.
5. [5] B. Hendrickson and T. G. Kolda, “Graph partitioning models for parallel computing,” Parallel Computing, Vol.26, No.12, pp. 1519-1534, 2000.
6. [6] I. S. Dhillon, “Co-clustering documents and words using bipartite spectral graph partitioning,” Proc. of the 7th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 269-274, 2001.
7. [7] U. V. Catalyurek and C. Aykanat, “Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication,” IEEE Trans. on Parallel and Distributed Systems, Vol.10, No.7, pp. 673-693, 1999.
8. [8] A. Gupta, “Fast and effective algorithms for graph partitioning and sparse-matrix ordering,” IBM J. of Research and Development, Vol.41, No.1.2, pp. 171-183, 1997.
9. [9] A. Gupta, G. Karypis, and V. Kumar, “Highly scalable parallel algorithms for sparse matrix factorization,” IEEE Trans. on Parallel and Distributed Systems, Vol.8, No.5, pp. 502-520, 1997.
10. [10] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.22, No.8, pp. 888-905, 2000.
11. [11] M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified NP-complete graph problems,” Theoretical Computer Science, Vol.1, No.3, pp. 237-267, 1976.
12. [12] T. Leighton and S. Rao, “An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms,” Proc. 1988 29th Annual Symp. on Foundations of Computer Science, pp. 422-431, 1988.
13. [13] T. N. Bui and B. R. Moon, “Genetic algorithm and graph partitioning,” IEEE Trans. on Computers, Vol.45, No.7, pp. 841-855, 1996.
14. [14] B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell System Technical J., Vol.49, No.2, pp. 291-307, 1970.
15. [15] C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for improving network partitions,” 19th Design Automation Conf., pp. 175-181, 1982.
16. [16] P. Chardaire, M. Barake, and G. P. McKeown, “A PROBE-based heuristic for graph partitioning,” IEEE Trans. on Computers, Vol.56, No.12, pp. 1707-1720, 2007.
17. [17] P. Merz and B. Freisleben, “Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning,” Evolutionary Computation, Vol.8, No.1, pp. 61-91, 2000.
18. [18] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning,” Operations Research, Vol.37, No.6, pp. 865-892, 1989.
19. [19] P. Eles, Z. Peng, K. Kuchcinski, and A. Doboli, “System level hardware/software partitioning based on simulated annealing and tabu search,” Design Automation for Embedded Systems, Vol.2, No.1, pp. 5-32, 1997.
20. [20] A. Steenbeek, E. Marchiori, and A. Eiben, “Finding balanced graph bi-partitions using a hybrid genetic algorithm,” 1998 IEEE Int. Conf. on Evolutionary Computation Proc., IEEE World Congress on Computational Intelligence, pp. 90-95, 1998.
21. [21] J. G. Martin, “Spectral techniques for graph bisection in genetic algorithms,” Proc. of the 8th Annual Conf. on Genetic and Evolutionary Computation, pp. 1249-1256, 2006.
22. [22] J. Kim, I. Hwang, Y.-H. Kim, and B.-R. Moon, “Genetic approaches for graph partitioning: a survey,” Proc. of the 13th Annual Conf. on Genetic and Evolutionary Computation, pp. 473-480, 2011.
23. [23] E. Rolland, H. Pirkul, and F. Glover, “Tabu search for graph partitioning,” Annals of Operations Research, Vol.63, No.2, pp. 209-232, 1996.
24. [24] R. Battiti and A. A. Bertossi, “Greedy, prohibition, and reactive heuristics for graph partitioning,” IEEE Trans. on Computers, Vol.48, No.4, pp. 361-385, 1999.
25. [25] M. Dell’Amico and F. Maffioli, “A new tabu search approach to the 0–1 equicut problem,” Meta-Heuristics, pp. 361-377, 1996.
26. [26] U. Benlic and J.-K. Hao, “An effective multilevel tabu search approach for balanced graph partitioning,” Computers & Operations Research, Vol.38, No.7, pp. 1066-1075, 2011.
27. [27] L. Sun and M. Leng, “An effective refinement algorithm based on swarm intelligence for graph bipartitioning,” Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, pp. 60-69, 2007.
28. [28] T. N. Bui and L. C. Strite, “An Ant System Algorithm For Graph Bisection,” Proc. of the 4th Annual Conf. on Genetic and Evolutionary Computation, pp. 43-51, 2002.
29. [29] G. v. Laszewski and H. Mühlenbein, “Partitioning a graph with a parallel genetic algorithm,” Int. Conf. on Parallel Problem Solving from Nature, pp. 165-169, 1990.
30. [30] H. Maini, K. Mehrotra, C. Mohan, and S. Ranka, “Genetic algorithms for graph partitioning and incremental graph partitioning,” Proc. of the 1994 ACM/IEEE Conf. on Supercomputing, pp. 449-457, 1994.
31. [31] U. Benlic and J.-K. Hao, “A multilevel memetic approach for improving graph k-partitions,” IEEE Trans. on Evolutionary Computation, Vol.15, No.5, pp. 624-642, 2011.
32. [32] H. Inayoshi and B. Manderick, “The weighted graph bi-partitioning problem: A look at GA performance,” Int. Conf. on Parallel Problem Solving from Nature, pp. 617-625, 1994.
33. [33] K. D. Boese, A. B. Kahng, and S. Muddu, “A new adaptive multi-start technique for combinatorial global optimizations,” Operations Research Letters, Vol.16, No.2, pp. 101-113, 1994.
34. [34] Y.-H. Kim and B.-R. Moon, “Investigation of the fitness landscapes in graph bipartitioning: An empirical study,” J. of Heuristics, Vol.10, No.2, pp. 111-133, 2004.
35. [35] A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, “Recent advances in graph partitioning,” Algorithm Engineering, pp. 117-158, 2016.
36. [36] C.-E. Bichot and P. Siarry, ”Graph Partitioning,” John Wiley & Sons, 2013.
37. [37] M. Armbruster, M. Fügenschuh, C. Helmberg, N. Jetchev, and A. Martin, “Hybrid Genetic Algorithm Within Branch-and-Cut for the Minimum Graph Bisection Problem,” Proc. of the 6th European Conf. on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2006, pp. 1-12, 2006.
38. [38] M. Boulif and K. Atif, “A new branch-&-bound-enhanced genetic algorithm for the manufacturing cell formation problem,” Computers & Operations Research, Vol.33, No.8, pp. 2219-2245, 2006.
39. [39] M. Boulif, “Genetic algorithm encoding representations for graph partitioning problems,” 2010 Int. Conf. on Machine and Web Intelligence (ICMWI), pp. 288-291, 2010.
40. [40] F. Rothlauf and D. E. Goldberg, “Redundant representations in evolutionary computation,” Evolutionary Computation, Vol.11, No.4, pp. 381-415, 2003.
41. [41] J. P. Cohoon and W. D. Paris, “Genetic placement,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol.6, No.6, pp. 956-964, 1987.
42. [42] T. N. Bui and B. R. Moon, “On Multi-Dimensional Encoding/Crossover,” Proc. of the 6th Int. Conf. on Genetic Algorithms, pp. 49-56, 1995.
43. [43] Z. Mehrdoost and S. S. Bahrainian, “A multilevel tabu search algorithm for balanced partitioning of unstructured grids,” Int. J. for Numerical Methods in Engineering, Vol.105, No.9, pp. 678-692, 2016.
44. [44] F. Ma, J.-K. Hao, and Y. Wang, “An effective iterated tabu search for the maximum bisection problem,” Computers and Operations Research, Vol.81, pp. 78-89, 2017.
45. [45] H. Meyerhenke, B. Monien, and T. Sauerwald, “A new diffusion-based multilevel algorithm for computing graph partitions,” J. of Parallel and Distributed Computing, Vol.69, No.9, pp. 750-761, 2009.
46. [46] C. Chevalier and I. Safro, “Comparison of coarsening schemes for multilevel graph partitioning,” Int. Conf. on Learning and Intelligent Optimization, pp. 191-205, 2009.
47. [47] A. J. Soper, C. Walshaw, and M. Cross, “A combined evolutionary search and multilevel optimisation approach to graph-partitioning,” J. of Global Optimization, Vol.29, No.2, pp. 225-241, 2004.
48. [48] Y. G. Saab, “An effective multilevel algorithm for bisecting graphs and hypergraphs,” IEEE Trans. on Computers, Vol.53, No.6, pp. 641-652, 2004.
49. [49] A. Arora and K. Kaur, “Enhanced Multilevel Hybrid Algorithm for Graph Partitioning,” Int. J. of Computer Applications, Vol.120, No.6, pp. 16-19, 2015.
50. [50] F. Xu, X. Ma, and B. Chen, “A new Lagrangian net algorithm for solving max-bisection problems,” J. of Computational and Applied Mathematics, Vol.235, No.13, pp. 3718-3723, 2011.
51. [51] P. Sanders and C. Schulz, “Think Locally, Act Globally: Highly Balanced Graph Partitioning,” Proc. of 12th Int. Symp. on Experimental Algorithms, pp. 164-175, 2013.
52. [52] P. Sanders and C. Schulz, “High quality graph partitioning,” Graph Partitioning and Graph Clustering (Contemporary Mathematics 588), pp. 1-17, 2013.
53. [53] D. LaSalle and G. Karypis, “A Parallel Hill-Climbing Refinement Algorithm for Graph Partitioning,” 2016 45th Int. Conf. on Parallel Processing (ICPP), pp. 236-241, 2016.
54. [54] S. Padmavathi and A. George, “Multilevel hybrid graph partitioning algorithm,” 2014 IEEE Int. Advance Computing Conf. (IACC), pp. 85-89, 2014.
55. [55] D. Kumar, A. Raj, D. Patra, and D. Janakiram, “GraphIVE: Heterogeneity-Aware Adaptive Graph Partitioning in GraphLab,” 2014 43rd Int. Conf. on Parallel Processing Workshops, pp. 95-103, 2014.
56. [56] B. Shams and M. Khansari, “Immunization of complex networks using stochastic hill-climbing algorithm,” ICCKE 2013, pp. 283-288, 2013.
57. [57] A. Pope, D. Tauritz, and A. Kent, “Evolving Bipartite Authentication Graph Partitions,” IEEE Trans. on Dependable and Secure Computing, p. 1, 2017.
58. [58] D. E. V. d. Bout and T. K. Miller, “Graph partitioning using annealed neural networks,” IEEE Trans. on Neural Networks, Vol.1, No.2, pp. 192-203, 1990.
59. [59] L. Sun and M. Leng, “An Effective Multi-level Algorithm Based on Simulated Annealing for Bisecting Graph,” Proc. of the 6th Int. Conf. on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), pp. 1-12, 2007.
60. [60] L. Li, Y. Song, and M. Gao, “A new genetic simulated annealing algorithm for hardware-software partitioning,” The 2nd Int. Conf. on Information Science and Engineering, pp. 1-4, 2010.
61. [61] T. Verbelen, T. Stevens, F. D. Turck, and B. Dhoedt, “Graph partitioning algorithms for optimizing software deployment in mobile cloud computing,” Future Generation Computer Systems, Special section: Recent advances in e-Science, Vol.29, No.2, pp. 451-459, 2013.
62. [62] F. Rahimian, A. H. Payberah, S. Girdzijauskas, M. Jelasity, and S. Haridi, “A Distributed Algorithm for Large-Scale Graph Partitioning,” ACM Trans. Auton. Adapt. Syst., Vol.10, No.2, Article No.12, pp. 1-24, 2015.
63. [63] H. N. Djidjev, G. Hahn, S. M. Mniszewski, C. F. A. Negre, A. M. N. Niklasson, and V. B. Sardeshmukh, “Graph Partitioning Methods for Fast Parallel Quantum Molecular Dynamics,” arXiv preprint, arXiv:1605.01118, 2016.
64. [64] A. Lim and Y.-M. Chee, “Graph partitioning using tabu search,” IEEE Int. Symp. on Circuits and Systems, pp. 1164-1167, 1991.
65. [65] J. Wu, P. Wang, S.-K. Lam, and T. Srikanthan, “Efficient heuristic and tabu search for hardware/software partitioning,” The J. of Supercomputing, Vol.66, No.1, pp. 118-134, 2013.
66. [66] R. Baños, C. Gil, J. Ortega, and F. G. Montoya, “A Parallel Multilevel Metaheuristic for Graph Partitioning,” J. of Heuristics, Vol.10, No.3, pp. 315-336, 2004.
67. [67] F. Curatelli, “Implementation and evaluation of genetic algorithms for system partitioning,” Int. J. of Electronics, Vol.78, No.3, pp. 435-447, 1995.
68. [68] C. H. Papadimitriou and K. Steiglitz, “Combinatorial optimization: algorithms and complexity,” Courier Corporation, 1982.
69. [69] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by simmulated annealing,” Science, Vol.220, No.4598, pp. 671-680, 1983.
70. [70] F. Glover, “Tabu search – part I,” ORSA J. on Computing, Vol.1, No.3, pp. 190-206, 1989.
71. [71] F. Glover, “Tabu search – part II,” ORSA J. on Computing, Vol.2, No.1, pp. 4-32, 1990.
72. [72] A. Svitenkov, P. Zun, O. Rekin, and A. G. Hoekstra, “Partitioning of Arterial Tree for Parallel Decomposition of Hemodynamic Calculations,” Procedia Computer Science, Vol.80, pp. 977-987, 2016.
73. [73] Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein, “Distributed GraphLab: a framework for machine learning and data mining in the cloud,” Proc. of the VLDB Endowment, Vol.5, No.8, pp. 716-727, 2012.
74. [74] S. Li, J. Zhang, K. Huang, and C. Gao, “A graph partitioning approach for Bayesian Network structure learning,” Proc. of the 33rd Chinese Control Conf., pp. 2887-2892, 2014.
75. [75] I. Tsamardinos, L. E. Brown, and C. F. Aliferis, “The max-min hill-climbing Bayesian network structure learning algorithm,” Machine Learning, Vol.65, No.1, pp. 31-78, 2006.
76. [76] G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM J. on Scientific Computing, Vol.20, No.1, pp. 359-392, 1998.
77. [77] G. Karypis and V. Kumar, “Multilevel k-way hypergraph partitioning,” VLSI Design, Vol.11, No.3, pp. 285-300, 2000.
78. [78] L. D. Belgacem and N. Puech, “Solving large size instances of the RWA problem using graph partitioning,” 2008 Int. Conf. on Optical Network Design and Modeling, pp. 1-6, 2008.
79. [79] S. B. H. Hassine, M. Jemai, and B. Ouni, “Power and Execution Time Optimization through Hardware Software Partitioning Algorithm for Core Based Embedded System,” J. of Optimization, Vol.2017, Article ID 8624021, 2017.
80. [80] H. Meyerhenke, P. Sanders, and C. Schulz, “Parallel graph partitioning for complex networks,” IEEE Trans. on Parallel and Distributed Systems, Vol.28, No.9, pp. 2625-2638, 2017.
81. [81] C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic, “Fennel: Streaming graph partitioning for massive scale graphs,” Proc. of the 7th ACM Int. Conf. on Web Search and Data Mining, pp. 333-342, 2014.
82. [82] Apache Giraph Project, http://giraph.apache.org/ [accessed March 9, 2018]
83. [83] G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, “Pregel: A System for Large-scale Graph Processing,” Proc. of the 2010 ACM SIGMOD Int. Conf. on Management of Data, SIGMOD ’10, pp. 135-146, 2010.
84. [84] C. Martella, D. Logothetis, A. Loukas, and G. Siganos, “Spinner: Scalable Graph Partitioning in the Cloud,” 2017 IEEE 33rd Int. Conf. on Data Engineering (ICDE), pp. 1083-1094, 2017.
85. [85] L. Wang, Y. Xiao, B. Shao, and H. Wang, “How to partition a billion-node graph,” 2014 IEEE 30th Int. Conf. on Data Engineering, pp. 568-579, 2014.
86. [86] I. S. Duff, R. G. Grimes, and J. G. Lewis, “Sparse matrix test problems,” ACM Trans. on Mathematical Software (TOMS), Vol.15, No.1, pp. 1-14, 1989.
87. [87] J. Leskovec, “SNAP: Stanford Network Analysis Project,” http://snap.stanford.edu [accessed March 12, 2018]
88. [88] T. A. Davis and Y. Hu, “The University of Florida sparse matrix collection,” ACM Trans. on Mathematical Software (TOMS), Vol.38, No.1, Article No.1, 2011.
89. [89] D. Bader, H. Meyerhenke, P. Sanders, and D. Wagner. “10th DIMACS implementation challenge,” AMS, 2012.
90. [90] D. A. Bader, H. Meyerhenke, P. Sanders, C. Schulz, A. Kappes, and D. Wagner, “Benchmarking for graph clustering and partitioning,” Encyclopedia of Social Network Analysis and Mining, pp. 73-82, 2014.