Fast Solving Maximum Weight Clique Problem in Massive Graphs

1 Introduction

The proliferation of massive data sets brings with it a series of special computational challenges. Many data sets can be modeled as graphs, and the research of massive realworld graphs grew enormously in last decade. A clique of a graph is a subset of the vertices that are all pairwise adjacent. Clique is an important graph-theoretic concept, and is often used to represent dense clusters. The maximum clique problem (MCP) is a long-standing problem in graph theory, for which the task is to find a clique with the maximum number of vertices in the given graph. An important generalization of MCP is the maximum weight clique problem (MWCP), in which each vertex is associated with a positive integer, and the goal is to find a clique with the largest weight. MWCP has valuable applications in many fields [Ballard and Brown, 1982; Balasundaram and Butenko, 2006; Gomez Ravetti and Moscato, 2008].

The decision version of MCP (and thus MWCP) is one of Karp's prominent 21 NP-complete problems [Karp, 1972], and is complete for the class W[1], the parameterized analog of NP [Fellows and Downey, 1998]. Moreover, MCP (and thus MWCP) is not approximable within n1-✏ for any ✏ > 0 unless NP=P [Zuckerman, 2007]. Nevertheless, these negative theoretical results have been established for "worst case", which does not often happen in practice. We still have hope of solving MWCP problems which arise in specific problem domains.

⇤Corresponding author

1.1 RelatedWork

Given their theoretical importance and practical relevance, considerable effort has been devoted to the development of various methods for MCP and MWCP, mainly including exact algorithms and heuristic algorithms. Exact algorithms can prove the optimality of their solutions, but they may fail to solve large graphs within reasonable time. On the other hand, various heuristic algorithms have been devised with the purpose of providing sub-optimal solutions within an acceptable time.

Almost all existing exact algorithms for MCP are branchand-bound (BnB) algorithms, and they differ from each other mainly by their techniques to determine the upper bounds and their branching strategies. A large family of BnB algorithms use coloring to compute upper bounds [Tomita and Seki, 2003; Tomita and Kameda, 2007; Konc and Janezic, 2007; Tomita et al., 2010; Segundo et al., 2013]. Another paradigm encodes MCP into MaxSAT and then applies MaxSAT reasoning to improve the upper bound [Li and Quan, 2010; Li et al., 2013]. There are also numerous works on heuristic algorithms for MCP, most of which are local search algorithms [Singh and Gupta, 2006b; Pullan and Hoos, 2006; Pullan, 2006; Guturu and Dantu, 2008; Benlic and Hao, 2013].

MWCP is more complicated than MCP and some powerful techniques for MCP are not applicable or ineffective for solving MWCP due to the vertex weights. This partly explains the fact that there are relatively fewer algorithms for MWCP. Some exact algorithms for MWCP come from and generalize previous BnB methods designed for MCP [ ¨Osterg˚ard, 1999; Kumlander, 2004]. The MaxSAT-based method is also generalized to MWCP, resulting in a state of the art exact MWCP algorithm named MaxWClq [Fang et al., 2014]. More efforts are devoted to heuristic algorithms for MWCP. Massaro et al. propose a complementary pivoting algorithm based on the corresponding linear complementarity problem [Massaro et al., 2002]. Busygin presents a heuristic method using a nonlinear programming formulation for MWCP [Busygin, 2006]. A hybrid evolutionary approach is offered in [Singh and Gupta, 2006a]. The Phased Local Search (PLS) algorithm is extended to MWCP [Pullan, 2008]. In [Wu et al., 2012], a local search algorithm called MN/NT integrates a combined neighborhood and a dedicated tabu mechanism, and shows better performance than previous heuristic algorithms. A recent local search algorithm based on the configuration checking strategy [Cai et al., 2011] called LSCC further improves MN/NT on a wide range of benchmarks [Wang et al., 2016].

Traditional algorithms usually become futile on massive graphs, due to their high space complexity and time complexity. For example, most traditional algorithms utilize adjacency matrix to facilitate fast computation of some operations such as the query of whether two vertices are adjacent. But the space requirement of this data structure is prohibitive for massive graphs. Also, most commonly used strategies do not have sufficiently low time complexity, which severely limits their ability to handle massive graphs.

Recently, there have been some dedicated algorithms for solving MCP in massive graphs. These MCP algorithms [Rossi et al., 2014; Verma et al., 2015] heavily depend on the concept of k-Core [Seidman, 1983], which is defined as a subgraph where all vertices have degree at least k, and can be computed in O(m) (m is the number of edges) using bin sorting [Batagelj and Zaversnik, 2003]. However, we are not aware of any work using the k-Core concept to develop MWCP algorithms. Moreover, an analogous concept in vertex weighted graphs requires prohibitive space (O(w · m), where w is the average weight of vertices) for bin sorting, and does not allow fast computation. As for MWCP, a recent progress in solving massive graphs is made in local search algorithms, by using a probabilistic heuristic called Best from Multiple Selection (BMS) [Cai, 2015]. BMS was first applied to minimum vertex cover problem [Cai, 2015], and then to MWCP, resulting in two efficient local search algorithms for MWCP called MN/TS+BMS and LSCC+BMS [Wang et al., 2016]. Seen from the literatures, LSCC+BMS is currently the best algorithm for solving MWCP in massive graphs.

1.2 Contributions and Paper Organization

Although recent works made progress in solving MWCP in massive graphs, the improvements are limited to local search and the performance is still not satisfactory. In many applications the time limit is very short, or the time resource is very valuable. This calls for more practical algorithms for solving MWCP in real-world massive graphs.

In this work, we propose an efficient method for solving MWCP in massive graphs, which interleaves between clique construction and graph reduction. In a graph reduction procedure, we reduce the size of the graph by removing some vertices that are impossible to be in any clique of the optimal weight. Most real-world massive graphs are power law graphs [Eubank et al., 2004; Lu and Chung, 2006], and can be reduced considerably by using a clique of certain quality in hand as a lower bound. On the other hand, a smaller graph presents smaller search space and the algorithm may find better cliques more easily, which can then be used to further reduce the graph. As far as we know, this is the first algorithm that interleaves between construction and reduction, although some previous MCP algorithms reduce the graph before calling an exact algorithm [Rossi et al., 2014; Verma et al., 2015].

Moreover, we propose three ideas to make the method effective and efficient. The fist one is a function for estimating the benefit of adding a vertex, which considers both the weight of the vertex and the weight of its effective neighborhood w.r.t the current clique. We also propose a dynamic BMS heuristic, which is used in choosing the adding vertex. Lastly but very importantly, we propose a fast and effective graph reduction algorithm, which relies on two reduction rules, including a novel branching-based reduction rule.

Based on these ideas, we develop an algorithm called FastWClq. Experiments on a wide range of real-world massive graphs show that, FastWClq finds better solutions than state of the art algorithms (including LSCC+BMS and MaxWClq) for most of the graphs with less run time. More encouragingly, FastWClq finds at least same-quality, sometimes betterquality solutions than its competitors even when the time limit for the competitors are 10 times and 36 times that for FastWClq. Further, FastWClq finds and proves the optimal solution for about half of the graphs in one second on average.

In the next section, we introduce some necessary background knowledge. Then, we describe our method in Section 3, including the FastWClq algorithm and its important components. Experimental evaluations of our algorithm FastWClq are presented in Section 4. Finally, we give some concluding remarks and outline the future work.

2 Preliminaries

Let G=(V ,E) be an undirected graph where V =¶v1, v2, ▷ ▷ ▷ , vn♦ is the set of vertices and E is the set of edges in G. We use V (G) and E(G) to denote the vertex set and the edge set of graph G. A vertex weighted undirected graph is an undirected graph G = (V↪E) combined with a weighting function w so that each vertex v 2 V is associated with a positive integer number w(v) as its weight. We use a triple to denote a vertex weighted graph, i.e., G = (V↪ E↪ w). For a subset S ✓ V , we let G[S] denote the subgraph induced by S, which is formed from S and all of the edges connecting pairs of vertices in S. The weight of S is w(S)=Pv2S w(v). The neighborhood of a vertex v is N(v)=¶u 2 V ♣¶u↪ v♦ 2 E♦, and we denote N[v] = N(v) [ ¶v♦. The degree of v is d(v) = ♣N(v)♣.

A graph G=(V ,E) is complete if its vertices are pairwise adjacent, i.e. 8u↪ v 2 V↪ ¶u↪ v♦ 2 E. A clique C is a subset of V such that the induced graph G[C] is complete. The maximum clique problem (MCP) is to find a clique of maximum cardinality in a graph, and the maximum weight clique problem (MWCP) is to find a clique of the maximum weight in a vertex weighted graph. A clique C is called a maximal clique in G if there exists no clique C 0 in G such that C 0 ⊃ C.

3 ANovel Method for MWCP

In this section, we propose an algorithm for solving MWCP called FastWClq, which interleaves between clique construction and graph reduction. We first describe the algorithm, and then introduce the important components of the algorithm.

The pseudo code of FastWClq is shown in Algorithm 1. On a top level, the algorithm works as follows. After some initializations, the algorithm executes a main loop until a limited time is reached, or an exact solution is found and proved. In each iteration of the loop, a clique is constructed by extending from an empty set (lines 3-15). To avoid ineffective construction procedures, we use pruning techniques to stop construction procedures that are known not to form a better clique than the best found clique. After the construction, if a better clique is obtained, the best found clique C ⇤ is updated, and then the graph is reduced (if possible) by iteratively applying reduction rules. Additionally, if the graph becomes empty after reduction, then the best found solution C ⇤ is proved to be optimal (as will be discussed in Section 3.2).

Now we describe the clique construction procedure. Let us first introduce some notation and definitions. We use C to denote the current clique under construction, and StartSet is the set containing vertices candidate as a starting vertex to construct a clique. CandSet = ¶v♣v 2 N(u) for 8u 2 C♦, i.e., each vertex in CandSet is adjacent to all vertices in C; this set consists of candidate vertices eligible to extend the current clique. The effective neighborhood of vertex v is defined as N(v) \ CandSet. The concept is very important, as w(N(v) \ CandSet) is used in both pruning a procedure and evaluating the quality of candidate vertices.

In a clique construction procedure, the algorithm first pops a random vertex from StartSet to serve as the starting vertex from which a clique will be extended, if StartSet is not empty (line 6). If StartSet becomes empty, which means all vertices have been used as the starting vertex, then another round of clique constructions begins by resetting StartSet to G(V ), and we adjust our strategy parameter (lines 3-5). After the starting vertex u is chosen, the clique is initialized with the vertex, and CandSet is initialized as N(u) (lines 7-8). Then, the clique is extended iteratively by each time adding a vertex v 2 CandSet (lines 9-15), until CandSet becomes empty. Also, we use a cost-effective upper bound to prune the procedure (lines 11-12). Obviously, w(C) + w(v) + w(N(v) \ CandSet) is an upper bound on weight of any clique extended from C by adding v and more vertices.

Although tighter upper bounds can be obtained by using more advanced techniques such as coloring, these bounds require much more time for computation. Our aim in this paper is to compute a high-quality solution in short time, so we do not use these techniques.

3.1 Choosing the Adding Vertex

An important component in FastWClq is the function ChooseAddV ertex (Algorithm 2), which selects a vertex from CandSet to extend the current clique. To this end, we propose a novel function to estimate the benefit of vertices, and a dynamic BMS heuristic to choose the adding vertex.

Benefit Estimation Function

Input: vertex weighted graph G = (V↪ E↪ w), the cutoff time Output: A clique of G StartSet = V (G), C⇤ := ;, k := k0; 1 while elapsed time < cutoff do 2 if StartSet = ; then 3 StartSet = V (G); 4 AdjustBMSnumber(k); 5 u := pop a random vertex from StartSet; 6 C := ¶u♦; 7 CandSet := N(u); 8 while CandSet 6= ; do 9 v := ChooseAddV ertex(CandSet↪ k); 10 if w(C) + w(v) + w(N(v) \ CandSet)  w(C⇤ ) 11 then Break; C := C [ ¶v♦; 12 CandSet := CandSet ∩ ¶v♦; 13 CandSet := CandSet \N(v); 14 if w(C) > w(C⇤ ) then 15 C⇤ := C; 16 G := ReduceGraph(G↪ C⇤ ); 17 StartSet = V (G); 18 if G becomes empty then 19 return C⇤ ; //exact solution 20 return C⇤ ; 21

We define the benefit of adding a vertex v as benefit(v) = w(Cf ) - w(C), where Cf is the final maximal clique grown from C [ ¶v♦. Note that we do not define benefit(v) as w(Cf) - w(C [ ¶v♦), because at this moment we do not know whether or not v will be selected to extend C.

An ideal strategy is to pick the vertex with the best benefit at each iteration to extend C. However, we cannot know the true benefit value of a vertex until we finish the construction procedure. In order to compare candidate vertices at the current iteration, we propose a function to estimate the benefit of adding a vertex. The function is based on two considerations:

1) If a candidate vertex v is added into the clique C, the weight of C is increased by w(v), which is a trivial lower bound of benefit(v).

2) Suppose a candidate vertex v is selected to be added into the clique C. The best possible weighted clique grown from C [ ¶v♦ is C [ ¶v♦ [ (N(v) \ CandSet), for which the weight is w(C) + w(v) + w(N(v) \ CandSet). Thus, an upper bound of benef it(v) is w(v) + w(N(v) \ CandSet).

We consider an estimation function should take into account both the lower bound and upper bound of benefit(v). A simple and intuitive function which embodies this principle is to take the average over these two bounds.

Dynamic BMS Heuristic

We choose the adding vertex based on their ˆb values according to a dynamic BMS (Best from Multiple Selection) heuristic. The original BMS heuristic is a probabilistic strategy which returns the best element frommultiple samples. It has been theoretically shown that BMS can approximate the best-picking strategy very well in O(1) time [Cai, 2015]. Another advantage of the BMS heuristic is that, we can control the greediness of the algorithm by adjusting the parameter k. However, this has not been exploited previously, and previous algorithms with BMS adopt a static BMS heuristic, that is, the number of samplings k stays the same.

if ♣CandSet♣ < k then 1 return a vertex v 2 CandSet with the greatest ˆb value; 2 v⇤ := a random vertex in CandSet; 3 for iteration := 1 to k - 1 do 4 v := a random vertex in CandSet; 5 if ˆb(v) > ˆb(v⇤ ) then v⇤ := v; 6 return v⇤ ; 7

In general, a greater k value indicates a greater greediness and more computation time. Based on this observation, we propose a dynamic BMS heuristic. In our algorithm, we start from a small k value (k0), so that the algorithm works fast. Whenever StartSet becomes empty, which means we do not find a better clique with this k value, we adjust k by increasing it as k := 2k, to make the algorithm construct cliques in a greedier way. Also, when k exceeds a predefined maximum value kmax, it is reset to k := ++k0. This is implemented in the function AdjustBMSnumber (line 5 in Algorithm 1).

3.2 Graph Reduction

By applying sound reduction rules (which usually depend on a clique in hand), a graph can be reduced to a smaller graph while keeping the optimal solution. This is desirable as algorithms can solve the original instance by solving a smaller and easier instance. In this subsection, we introduce a graph reduction algorithm, which relies on two reduction rules, including a novel branching-based reduction rule.

Definition 1 Given a vertex weighted graph G = (V↪ E↪ w), for a vertex v 2 V (G), an upper bound on the weight of any clique containing v is an integer, denoted as UB(v), such that UB(v) ≥ max¶w(C)♣C is a clique of G↪ v 2 C♦.

Now, we consider the following reduction rule.

Rule: Given a vertex weighted graph G = (V↪ E↪ w) and a clique C0 in G, 8v 2 V (G), if there is an upper bound UB(v) such that UB(v)  w(C0), then delete v and its incident edges fromG.

The above rule indeed represents a family of reduction rules, and in order to obtain an applicable concrete rule, we need to specify the upper bound function and the input clique. We use the notation Rule(UB↪ C0) to denote a concrete rule where UB is the upper bound function and C0 is the input clique.

Proposition 1 Let G be a vertex weighted graph, G0 the resulting graph by applying Rule(UB↪C0) on G, and let w⇤ be the weight of the maximum weight clique of graph G, and C ⇤G0 the maximum weight clique of G0 . Then, w⇤ = max¶w(C0)↪ w(C ⇤G0 )♦.

Proof: If w(C0) = w⇤ , then the proposition obviously holds. Now we consider the case w(C0) < w⇤ . For graph G and a vertex v 2 V (G), let C ⇤ (v) be the clique s.t. v 2 C ⇤ (v) and w(C ⇤ (v)) ≥ w(C) for any clique C containing v. By Definition 1, we have w(C ⇤ (v))  UB(v). On the other hand, any vertex deleted by Rule(UB↪ C0) satisfies UB(v)  w(C0), and thus w(C ⇤ (v))  UB(v)  w(C0) < w⇤ , meaning that v cannot be contained in any clique with weight w⇤ . Thus, any vertex that is in a clique with weight w⇤ remains in G0 , so w⇤ = w(C ⇤G0 ). ⇤

The above proposition shows that any rule in family Rule is sound w.r.t. keeping the optimal solution of the instance. Additionally, the proposition leads to the following corollary.

Corollary 1 Let G0 be the resulting graph by applying Rule(UB↪C0) on vertex weighted graph G, if V (G0 ) = ;, then C0 is the maximum weight clique of G.

Given a clique in hand (by construction as shown in Algorithm 1), in order to apply reduction rules, the focus is how to compute an upper bound. Since any clique grown from vertex v can only contain vertices in N(v), a trivial upper bound function is

To get a tighter bound for vertex v, we consider its neighboring vertex with the maximum weight (denoted as n⇤ ). The idea is that, for any clique C containing v, it either contains n⇤ or it does not. For either case, we can have a tighter upper bound than UB0(v), and finally we get the larger (worse) one as the upper bound. We divide the cases on n⇤ in order to balance the bounds of the two cases. Formally, we propose a branching-based upper bound as follows:

Note that we use adjacency list instead of adjacency matrix for the purpose of saving space. So, checking whether a vertex y 2 N(v) is in N(n⇤ ), i.e., whether y and n⇤ are neighbors, requires O(min¶d(y)↪ d(n⇤ )♦) time, which indicates a square time complexity for computing N(v)\N(n⇤ ) by each time checking whether a vertex in N(v) is in N(n⇤ ). In this work, rather than use the above implementation, we use a linear implementation to compute N(v) \N(n⇤ ) (two scans on the smaller set and one on the larger one), by using indicators.

The graph reduction algorithm is depicted in Algorithm 3. Both upper bounds are used. UB0 requires little overhead, while UB1 requires more computation time but is tighter. Therefore, when considering a vertex, we first use the UB0 based reduction rule, and if this cannot delete the vertex then we apply the rule based on UB1 1 .

Our reduction algorithm works in an iterative fashion, with a queue called RmQueue which contains vertices to be deleted. In the beginning, the algorithm enqueues all vertices satisfying at least one of the reduction rules into RmQueue. Then, a loop is carried out until RmQueue becomes empty. Each iteration of the loop pops a vertex u from RmQueue, and deletes u and all its incident edges fromG. After a vertex u is deleted, we check its remained neighborhood Nr(u) (the set containing all neighbors of u that have not been removed from the graph yet), and add all vertices in Nr(u) that satisfy at least one of the reduction rules into RmQueue.

1 In practice, a trick to accelerate the procedure (slightly) for large-sized graphs is to first use UB0 to reduce the graph to a certain size, after which UB1 will be used.

Input: vertex weighted graph G = (V↪ E↪ w), a clique C0 Output: A simplified graph of G foreach v 2 V (G) do 1 if UB0(v)  w(C0) -- UB1(v)  w(C0) then 2 RmQueue := RmQueue [ ¶v♦; 3 while RmQueue 6= ; do 4 u := pop a vertex from RmQueue; 5 delete u and its incident edges fromG; 6 foreach v 2 Nr(u) do 7 if UB0(v)  w(C0) -- UB1(v)  w(C0) then 8 RmQueue := RmQueue [ ¶v♦; 9

Algorithm 3: ReduceGraph (G, C0) return G; 10

According to Corollary 1, if the ReduceGraph algorithm returns an empty graph, that means the found clique is an optimal weighted clique of the input graph. However, there are cases that FastWClq finds an optimal weighted clique but ReduceGraph cannot reduce the graph to empty, because the reduction rules are incomplete.

4 Experimental Evaluation

We carry out experiments to evaluate FastWClq on a broad range of real-world massive graphs. We compare FastWClq against the currently best heuristic MWCP algorithm LSCC+BMS [Wang et al., 2016], and the currently best exact algorithmMaxWClq [Fang et al., 2014].

4.1 Experimental Preliminaries

The benchmarks in our experiments were originally from the Network Data Repository online [Rossi and Ahmed, 2015], 2 including biological networks, collaboration networks, facebook networks, interaction networks, infrastructure networks, amazon recommend networks, retweet networks, scientific computation networks, social networks, technological networks, and web link networks. The original benchmarks are unweighted, and we transformed them into a vertex weighted version: For the ith vertex vi, w(vi)=(i mod 200)+1.There are totally 102 graphs. Many of these real-world graphs have millions of vertices and dozens of millions of edges. These benchmarks have been used in evaluating MWCP algorithms [Wang et al., 2016], as well as algorithms for Maximum Clique [Rossi et al., 2014], Coloring [Rossi and Ahmed, 2014] and Minimum Vertex Cover problems [Cai, 2015].

FastWClq is implemented in C++. Parameters k0 and kmax for dynamic BMS heuristic are set to 4 and 64 (=26 ). LSCC+BMS and MaxWClq were implemented in C++ by their authors. All algorithms are complied with g++ version 4.7 with -O3 option.

2 http://www.graphrepository.com/networks.php

The experiments are carried out on a workstation under Ubuntu Linux 14.04, using 2 cores of Intel i7-4710MQ CPU @ 2.50 GHz and 32 GByte RAM. We run FastWClq and LSCC+BMS 10 times on each graph. The cutoff time ("ct") for FastWClq is 100 seconds per run. For LSCC+BMS, we test it under two cutoff time, 100 and 1000 seconds. This is to justify that the solutions found by FastWClq are sufficiently good even compared with those found by LSCC+BMS under 10 more time limit. For the exact algorithm MaxWClq, we run it once on each graph with a cutoff time of one hour.

For each graph, we report the best clique weight ("Best") found by each algorithm, and the average clique weight over all runs ("Avg") if a 100 percent success rate is not reached. If an algorithm fails to provide a solution for an instance, then the corresponding column is marked as "N/A". If an algorithm proves the optimal solution, the corresponding column is marked with a "*". Due to the limited space, we do not report the run time for each graph; instead, we report the averaged run time for each graph family (Table 3).

4.2 Experimental Results

Part 1: We first compare the algorithms in terms of solution quality. The results are presented in Tables 1 and 2. To make the comparison between FastWClq and other algorithms more clear, for a comparing algorithm, if the solution quality is worse than that found by FastWClq, then we mark it with "#", and if it is better we mark it with """.

There are 12 graphs that have less than 1000 vertices, where all the algorithms find the optimal solution within a few seconds, and thus they are not reported.For the remaining 90 instances, FastWClq always finds a better or equal-quality solution compared to its competitors, with only one exception. FastWClq performs better on 47 instances than LSCC+BMS under the same cutoff time (100s), and performs better on 27 instances when the cutoff time for LSCC+BMS extends to 1000s. The exact solver MaxWClq fails on most of these graphs, yet it proves the optimal solution for 29 instances (including the 12 small instances), all of which have less than 12 thousand vertices. FastWClq proves the optimal solution for 46 instances, including 7 instances with millions of vertices, and the largest one that has 24 million vertices (inf-road-usa). The local search algorithm LSCC+BMS is essentially unable to prove the optimality of the solution.

Part 2: We now compare run time of the algorithms, which is summarized in Table 3. For each family, we calculate average run time over all runs for each instance, and report the average value of these average run time. If an algorithm fails to find a solution in all runs (marked with "N/A"), its run time is considered to be the cutoff time on that instance.

FastWClq is usually orders of magnitude faster than the other two algorithms. Indeed, if we run LSCC+BMS with longer time to get the same quality solution by FastWClq (if possible), the run time of LSCC+BMS would be much longer. Moreover, FastWClq proves the optimal solution for 46 instances with the averaged time of 0.902 second, and exactly solves the largest instance with 24 million vertices (inf-roadusa) in 5.67 seconds. To summarize, FastWClq finds optimal or sub-optimal solutions for theses graphs within a few seconds on average, and solves many graphs in one second.

1367(1349.8) #

N/A #

5 Conclusions and FutureWork

This paper presented a novel method for Maximum Weight Clique problem (MWCP), which aims to solve massive graphs within short time. The method interleaves between clique construction and graph reduction. Three ideas were proposed to improve the algorithm, including a benefit estimation function, a dynamic BMS heuristic, and a graph reduction algorithm. The resulting algorithm is called FastWClq. Experiments on real-world massive graphs show that, FastWClq finds better solutions than state of the art algorithms while the run time is much less, even when the time limit for the competitor is much more. Also, FastWClq proves the optimal solution for about half of the tested graphs in one second, including graphs with millions of vertices.

A significant direction is to apply this "Construction and Reduction" method and the ideas to other graph problems.

Acknowledgement

This work is supported by 973 Program 2014CB340301 and National Natural Science Foundation of China 61502464.

3455(1370) # 3455(2405.3) # N/A #