Local search for the maximum k -plex problem
- PDF / 327,406 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 197 Views
Local search for the maximum k-plex problem Wayne Pullan1 Received: 21 January 2020 / Revised: 1 July 2020 / Accepted: 24 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The maximum k-plex problem is an important, computationally complex graph based problem. In this study an effective k-plex local search (KLS) is presented for solving this problem on a wide range of graph types. KLS uses data structures suitable for the graph being analysed and has mechanisms for preventing search cycling and promoting search diversity. State of the art results were obtained on 121 dense graphs and 61 large real-life (sparse) graphs. Comparisons with three recent algorithms on the more difficult graphs show that KLS performed better or as well as in 93% of 332 significant k-plex problem instances investigated achieving either larger average k-plex sizes (including some new results) or, when these were equivalent, lower CPU requirements. Keywords NP-complete · Heuristic · Local search · k-plex · Large graphs
1 Introduction Given an undirected graph G = (V , E) where V = {v1 , . . . , vn } is the set of vertices and E ⊂ V × V is the set of edges, a k-plex for a given positive integer k is a subset S of V where each vertex of S is adjacent to at least |S| − k vertices in the subgraph (S, E ∩ S × S). The k-plex problem with k = 1 reduces to the maximum clique problem and is NP-complete (Balasundaram et al. 2011) for all k ≥ 1. While there has been extensive investigation of the maximum clique problem, relatively little effort has been applied to the k-plex problem. However, because of the variety of real world applications for k-plex (including social networks, information retrieval, classification theory) this is now changing and over recent time several exact algorithms (Balasundaram et al. 2011; McClosky and Hicks 2012; Moser et al. 2012; Trukhanov et al. 2013) have been developed. However these methods typically fail
The source code for KLS is available from the author.
B 1
Wayne Pullan [email protected] School of Information and Communications Technology, Griffith University, Gold Coast, Australia
123
W. Pullan
on larger problems so effort has gone into developing heuristic approaches including (Gujjula et al. 2014) which is based on the GRASP framework, a frequency based tabu search algorithm FD-TS (Zhou and Hao 2017), breakout local search incorporating reinforcement learning BLS-RLE (Jin et al. 2019), and reinforcement learning with configuration checking DCCplex (Chen et al. 2020). In this paper k-plex local search (KLS), a new greedy/least used heuristic algorithm for the maximum k-plex problem is presented. Experiments show that KLS is competitive on a wide range of graph types (small−large, sparse−dense) when compared with the FD-TS, BLS-RLE and DCCplex algorithms. The remainder of this paper is organised as follows: Sect. 2 presents KLS, the proposed local search for solving the k-plex. Section 3 contains a time and complexity analysis for KLS while Sect. 4 prese
Data Loading...
