An Exact Algorithm For Maximum Weight K-Plexes On Massive Sparse Graphs

In an undirected graph G=(V,E),a clique refers to a complete subgraph where any two vertices in the subgraph are connected by an edge.A k-plex refers to a subgraph of G where each node is nonadjacent to at most(k-1)other nodes.In a given graph G,the Maximum k-plex Problem looks for a clique with the most vertices.The Maximum Weighted k-plex Problem aims to identify the subset of G with the highest weight,where each node is given a weight greater than zero,the subset satisfies the k-plex definition,and the weight of the subset is the sum of the weights of all the nodes in the subset.The Weighted Maximum k-plex Problem is a classic NP-hard problem and has wide applications in various fields such as bioinformatics,computer vision,coding theory,fault diagnosis,social circle analysis,and economic analysis.It is closely connected to other well-known NP-hard issues like Graph Coloring,Maximum Clique,and Maximum Independent Set.There is tremendous theoretical and practical importance in researching algorithms for the Weighted Maximum K-Plex Problem.Today,branch-and-bound search algorithms and heuristic local search algorithms are the two main approaches for overcoming these issues.The former frequently places a focus on speed in an effort to swiftly arrive at a somewhat ideal answer,but the likelihood of doing so is low.The latter ensures that the global optimal solution is reached and needs scanning the whole problem’s solution space in order to accurately acquire the optimal answer.Nevertheless,these techniques frequently require a lot of time and are ineffective because of the exponential temporal complexity.Heuristic algorithms are frequently favored in practical situations when it is vital to balance speed and solution quality.The weighted maximum k-plex issue will continue to be a key research subject because of the advancements in computer power and algorithm development,which have substantially enhanced the practical solving capabilities of accurate methods.Researchers must overcome difficulties like lengthy algorithm solving times and high memory requirements.This study focuses on the precise branch-and-bound approach for the weighted maximum k-plex issue on large-scale sparse graphs.The following three aspects of the particular work are reflected:(1)We studied the exact algorithm for solving the maximum k-plex problem and developed an exact algorithm,named MWKP,based on the branch and bound method for the weighted maximum k-plex problem.(2)By analyzing the properties of k-plex,we derived some deduction rules and designed new upper bound estimation formulas during the search process.We also provided reduction methods during the search process to improve the search efficiency of the MWKP algorithm.(3)To address sparse large graphs in the real world,with the primary goal of reducing the number of branching vertices,we designed a preprocessing program to reduce the initial graph.This program aims to minimize the size of the graph during the search process,thereby narrowing down the search scope of the MWKP algorithm and improving the overall algorithm speed.The algorithm has significant advantages over existing exact algorithms for weighted maximum k-plex problems in terms of program running efficiency and results,according to experimental results.Additionally,the algorithm’s ability to solve largescale sparse graphs has been significantly improved,increasing the practical applicability of exact algorithms.