Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive Graphs

1 Introduction

The rapid growth of the Internet, the widespread deployment of sensors and scientific advances have resulted in more and more massive data sets. This has brought a series of computational challenges, as existing algorithms usually become ineffective on massive data sets, and for most problems we need to develop new algorithms. Many data sets can be modeled as graphs, and the study of massive real world graphs, also called complex networks, grew enormously in last decade.

A vertex cover of a graph is a subset of the vertices which contains at least one of the two endpoints of each edge. Alternatively, a vertex cover is a set of vertices whose removal completely disconnects a graph. The MinVC problem is to find the minimum sized vertex cover in a graph. MinVC is a prominent combinatorial optimization problem with important applications, including network security, industrial machine assignment and applications in sensor networks such as monitoring link failures, facility location and data aggregation [Kavalci et al., 2014]. It is also closely related to the Maximum Independent Set (MaxIS) problem, which has applications in social networks, pattern recognition, molecular biology and economics [Jin and Hao, 2015].

MinVC is a classical NP-hard problem which remains intractable even for cubic graphs and planar graphs with maximum degree at most three [Garey and Johnson, 1979]. Furthermore, it is NP-hard to approximate MinVC within any factor smaller than 1.3606 [Dinur and Safra, 2005], although one can achieve an approximation ratio of 2 - o(1) [Karakostas, 2005].

1.1 Previous Heuristics andMotivations

Due to its NP-hardness, the research of MinVC solving is concentrated on heuristic algorithms for finding a "good" vertex cover in reasonable time. One of the most popular and efficient heuristic approaches is local search, and there has been considerable interest in local search algorithms for MinVC in last decade, e.g., [Shyu et al., 2004; Richter et al., 2007; Andrade et al., 2008; Pullan, 2009; Cai et al., 2010; 2011; 2013]. Especially, a recent algorithm called NuMVC [Cai et al., 2013], which clearly dominates other local search MinVC algorithms, makes a significant improvement in MinVC solving.

Previous local search algorithms for MinVC are mainly evaluated on standard benchmarks from the academy community, particularly the DIMACS and BHOSLIB benchmarks [Richter et al., 2007; Andrade et al., 2008; Pullan, 2009; Cai et al., 2010; 2011; 2013]. To improve the performance of the algorithms on these benchmarks, researchers have proposed sophisticated heuristics for local search for MinVC. Recent heuristics include max-gain vertex pair selection [Richter et al., 2007], edge weighting [Richter et al., 2007; Cai et al., 2010], k-improvement (also called (k-1, k) swap) [Andrade et al., 2008], configuration checking [Cai et al., 2011], minimum loss removing and two-stage exchange [Cai et al., 2013]. Most of the previous heuristics do not have sufficiently small complexity. Because the benchmark graphs used for testing previous algorithms are not large (usually with less than five thousand vertices), the complexity of heuristics did not show an obvious impact on the performance. However, for massive graphs where the size is much larger (e.g., with millions of vertices), the high complexity severely limits the ability of algorithms to handle these data sets.

Massive graphs call for new heuristics and algorithms. However, there is little (if any) work being done on local search algorithms for massive graphs. In particular, we are not aware of any research on local search for MinVC on massive graphs. In this work, we make a first step and provide key insights in this direction. In our opinion, more attention needs to be applied to the time complexity of heuristics when designing algorithms for solving massive graphs. The key issue is on making a good balance between the time efficiency and the guidance effectiveness of heuristics.

1.2 Contributions and Paper Organization

In this paper, we design and implement a new local search algorithm for MinVC called FastVC, which is dedicated to solving massive graphs. The main principle is to use lowcomplexity approximate heuristics rather than those accurate heuristics with high complexity. To achieve good performance on massive graphs, we propose two new heuristics, which form the two key components of FastVC.

Firstly, we propose a fast heuristic for constructing a vertex cover. The obtained vertex cover will be used as the initialized candidate solution for local search. The heuristic considers an edge in each iteration, and if the edge is uncovered, it picks the endpoint with the higher degree to cover it. After a vertex cover is obtained, redundant vertices are removed by a read-one procedure on the vertex cover. This heuristic has a complexity of O(|E|), compared to O(|V |2 ) for the greedy construction heuristic used in previous algorithms.

We also propose a cost-effective heuristic for choosing the vertex for removing in each step. The heuristic is named Best from Multiple Selections (BMS), which approximates the minimum loss removing heuristic [Cai et al., 2013] very well and lowers the complexity from O(|V |) to O(1).

We carry out experiments to compare FastVC with NuMVC on a broad range of massive real world graphs. Experimental results show that FastVC finds significantly better quality vertex covers (and thus also independent sets) than NuMVC on most instances. Note that this improvement is remarkable, as it rarely happens in the literature to find a better solution. Previous MinVC algorithms often obtain the same quality solutions and they focus on comparing the success rate of finding a solution of such a quality.

In the next section, we introduce some necessary background knowledge. Then, we describe the FastVC algorithm in Section 3, and present two key functions based on the two new heuristics and provide some theoretical results in Section 4. Experimental evaluations of FastVC are presented in Section 5. Finally, we give some concluding remarks.

2 Preliminaries

2.1 Basic Definitions and Notation

An undirected graph G = (V,E) consists of a vertex set V and an edge set E where each edge is a 2-element subset of V . For an edge e = {u, v}, we say that vertices u and v are the endpoints of edge e. Two vertices are neighbors if and only if they both belong to some edge. The neighborhood of a vertex v is denoted as N(v) = {u ∈ V |{u, v} ∈ E}, and the closed neighborhood as N[v] = {v} ∪ N(v). The degree of a vertex v is defined as deg(v) = |N(v)|. An edge e ∈ E is covered by a vertex set S if at least one endpoint of e belongs to S, and otherwise it is uncovered.

For an undirected graph G = (V,E), a vertex cover of a graph is a subset of V which contains at least one of the two endpoints of each edge, and an independent set is a subset of V where no two vertices are neighbors. A vertex set S is a vertex cover of G if and only if V \S is an independent set of G. We are concerned in this paper with the problem of finding a vertex cover as small as possible (MinVC). Equivalently, this problem can be viewed as seeking for an independent set as large as possible, which also has important applications.

2.2 Preliminaries of Local Search for MinVC

One popular way to solve the MinVC problem is based on iteratively solving its decision version - given a positive integer number k, searching for a k-sized vertex cover. The general scheme is as follows: In the beginning, a vertex cover is constructed; whenever the algorithm finds a vertex cover of k vertices, one vertex is removed from the vertex cover 1 , and the algorithm starts from the resulting vertex set to search for a vertex set of k - 1 vertices that covers all edges (i.e., a vertex cover of k - 1 vertices) by performing local search.

We denote the current candidate solution as C, which is a vertex set containing the vertices selected for covering. For a vertex v ∈ C, the loss of v, denoted as loss(v), is defined as the number of covered edges that would become uncovered by removing v from C. For a vertex v /∈ C, the gain of v, denoted as gain(v), is defined as the number of uncovered edges that would become covered by adding v into C. Both loss and gain are scoring properties of vertices. The age of a vertex is the number of steps since its state was last changed.

For local search MinVC algorithms based on iteratively solving the decision problem, each search step consists of exchanging a pair of vertices: a vertex u ∈ C is removed from C, and a vertex v /∈ C is put into C. Such a step is called an exchanging step. In the literature, there are two ways to perform an exchanging step. The first one is adopted by algorithms before NuMVC, which chooses a vertex pair from candidate vertex pairs, and then exchanges them and updates scoring properties accordingly. The second method, proposed in NuMVC and named two-stage exchange, works in a "separate" fashion: it first chooses a vertex u ∈ C and removes it, and updates scoring properties accordingly, and then chooses a vertex v /∈ C and adds it, and updates scoring properties accordingly.

3 FastVC: the Top-Level Algorithm

This section describes the FastVC algorithm on a top level. Details of important functions in FastVC and further analysis will be presented in the next section.

FastVC solves the MinVC problem by iteratively solving its decision version. For the exchanging step in local search, FastVC adopts the two-stage exchange framework, as it has lower complexity than the alternative paradigm based on vertex pair exchange. Indeed, as shown in [Cai et al., 2013], thanks to the two-stage exchange framework, NuMVC

1 if after removing one vertex, the vertex set remains a vertex cover, then more vertices are removed until it is not a vertex cover.

Algorithm 1: FastVC (G, cutoff)

Input: graph G = (V,E), the cutoff time Output: vertex cover of G C := ConstructV C(); 1 gain(v) := 0 for each vertex v /∈ C; 2 while elapsed time < cutoff do 3 if C covers all edges then 4 C∗ := C; 5 remove a vertex with minimum loss from C; 6 continue; 7 u := ChooseRmV ertex(C); 8 C := C\{u}; 9 e := a random uncovered edge; 10 v := the endpoint of e with greater gain, breaking ties in 11 favor of the older one; C := C ∪ {v}; 12 return C∗ ; 13

performs several times more steps per second than other local search MinVC algorithms, which is a main factor of its good performance.

The top-level algorithm of FastVC is outlined in Algorithm 1, as described below. In the beginning, a vertex cover is constructed by the ConstructVC function, which is taken as the initialized candidate solution C for the algorithm. The loss values of vertices in C are calculated in the ConstructVC function. For vertices outside C, their gain values are set to 0, as at this point all edges are covered by C and adding any vertex into C would not increase the number of covered edges.

Now we introduce the exchanging step in FastVC. At each step, the algorithm first chooses a vertex in u ∈ C to remove, which is accomplished by the ChooseRmV ertex function. Then, the algorithm picks a random uncovered edge e, and chooses one of e's endpoints with the greater gain and adds it into C, breaking ties in favor of the older one. Note that along with removing or adding a vertex, the loss and gain values of the vertex and its neighbors are updated accordingly.

4 Main Functions and Analysis

Two important components of the FastVC algorithm are the ConstructVC function and the ChooseRmV ertex function. In this section, we present these two functions in detail, and provide some theoretical analysis on them.

4.1 Fast Construction of Vertex Cover

Local search algorithms for MinVC based on iteratively solving the decision problem starts with a vertex cover, and we call it the starting vertex cover. A small starting vertex cover can save the subsequent local search from too much unnecessary search before beginning the search for a good solution. A balance much be struck between the quality of the starting vertex cover and the time consumed in constructing it. Otherwise, the resulting algorithm may be inefficient in practice. For convenience of discussions on complexity, let us denote n = |V |, m = |E|.

Previous Construction Heuristic

Previous local search algorithms for MinVC construct the starting vertex cover using an intuitive greedy procedure [Papadimitrious and Steiglitz, 1982] which works as follows:

Repeat the following operations until C becomes a vertex cover: select a vertex v /∈ C with the maximum gain to add into C, breaking ties randomly.

The number of iterations of this procedure equals the size of the obtained vertex cover C, and is denoted as ℓ. We analyze the worst case complexity for two implementations of the above algorithm as follows:

A straight-forward implementation is to scan the vertex set V in each iteration in order to find the objective vertex, which has a complexity of Θ(n) for each iteration. Therefore, the complexity is Θ(ℓ · n) = O(n2 ).

A more "clever" implementation is to maintain the C set and also a set of vertices not in C, which is denoted as H. In each iteration, we scan the H set to find a vertex with the maximum gain. To be precise, we use Ci and Hi to denote the C set and H set at the beginning of the ith iteration. We have |Ci| = i - 1 and |Hi| = n - |Ci| = n - (i - 1). Thus, ∑ℓi=1 |Hi| = ∑ℓi=1 (n - (i - 1)) = 12 ℓ(2n + 1 - ℓ). Since 1 ≤ ℓ ≤ n ⇒ 12 ℓ(n + 1) ≤ 12 ℓ(2n + 1 - ℓ) ≤ ℓn, we have ∑ℓi=1 |Hi| = Θ(ℓ ·n). Therefore, the complexity of this implementation is ∑ℓi=1 |Hi| = Θ(ℓ · n) = O(n2 ).

Although using "clever" implementations can accelerate the heuristic, the complexity remains square. We will see from the experiment results in Section 5.3 that, a square complexity is too high for massive graphs and makes the algorithms inefficient so that they may fail to provide a vertex cover within reasonable time (like 1000 seconds).

The ConstructVC Procedure

Our first step to build a fast local search algorithm for MinVC is to propose a fast vertex cover construction procedure, which is the ConstructV C procedure in FastVC.

The proposed procedure (Algorithm 2) consists of an extending phase and a shrinking phase.

The extending phase: Starting with an empty set C, the algorithm extends C by checking and covering an edge in each iteration: if the considered edge is uncovered, the endpoint with a higher degree is added into C. Obviously, we obtain a vertex cover at the end of the extending phase.

The shrinking phase: First, we calculate the loss values of vertices in C; then, we scan the C set and if a vertex v ∈ C has a loss value of 0, it is removed, and loss values of its neighbors are updated accordingly.

Theorem 1. The vertex set returned by the ConstructVC procedure is a minimal vertex cover. 2

Proof. Let us denote the vertex cover produced by the extending phase as C = {vi1 , vi2 , vi3 , ..., viℓ }, which may be modified in the shrinking phase. In the j th iteration of the shrinking phase, we consider vertex vij .

(a) We first prove that the vertex set returned by the procedure is a vertex cover. At the beginning of the shrinking phase, C is a vertex cover. Suppose at the j th iteration of the shrinking phase, C is a vertex cover, we will prove that at the (j + 1)th iteration, C is a vertex cover. If loss(vij+1 ) > 0, then C does not change; if loss(vij+1 ) = 0, then vij+1 is removed, but according to the definition of loss, removing such a vertex would not generate any new uncovered edge. Hence, C is a vertex cover after the shrinking phase.

2 A vertex cover is minimal if taking any vertex out of it would make it not a vertex cover.

(b) Now we prove that the vertex cover C after the shrinking phase is minimal. Suppose after the shrinking phase, there exists a vertex in C whose removal keeps C a vertex cover. Without the loss of generality, let this vertex be vij , the one considered at the j th iteration of the shrinking phase. From the assumption, we have loss(vij ) = 0 at the end of the shrinking phase. Notice that during the shrinking phase, the loss value of any vertex in C does not decrease (according to Lemma 1). Thus, the value of loss(vij ) at the j th iteration is at most 0, but loss values are non-negative, so it is 0. Therefore, vij would have been removed at the j th iteration. This completes the proof by contradiction.

Input: graph G = (V, E) Output: vertex cover of G C := ∅; 1 //extend C to cover all edges 2 foreach e ∈ E do 3 if e is uncovered then 4 add the endpoint of e with higher degree into C; 5 //calculate loss of vertices in C 6 loss(v) := 0 for each v ∈ C; 7 foreach e ∈ E do 8 if only one endpoint of e belongs to C then 9 for the endpoint v ∈ C, loss(v)++; 10 //remove redundant vertices 11 foreach v ∈ C do 12 if loss(v) = 0 then 13 C := C\{v}, update loss of vertices in N(v); 14 return C; 15

Lemma 1. For any iteration of the shrinking phase, the execution of the iteration does not decrease the loss value of any vertex in C.

Proof. Consider any iteration in the shrinking phase. For

simplicity, we use v to denote the vertex under consideration.

If loss(v) > 0, the iteration does nothing and thus the lemma holds.

Now we consider the case loss(v) = 0. This indicates all vertices in N(v) belong to C. Otherwise, if there is a vertex v′ ∈ N(v) such that v′ /∈ C, then removing v would would make the edge e = {v, v′ } uncovered, which means loss(v) is at least one. So, in the case loss(v) = 0, v is removed, and along with that, the loss value of each vertex v′ ∈ N(v) is increased by one, as after this iteration, the removal of v′ would make the edge e = {v, v′} from covered to uncovered. For vertices not in N(v), their loss values do not change.

Complexity of ConstructVC: The ConstructVC procedure can be divided into three parts: the first part (lines 35) performs the extending phase, the second part (lines 7-10) initializes the loss values, while the last one (lines 12-14) removes redundant vertices.

Let C + denotes the vertex cover obtained by the extending phase. It is clear that the complexity of the extending phase is O(m). For the second part, the complexity is O(|C +| + m). Since at most one vertex is added in each iteration of the extending phase, we have |C+| ≤ m, and thus the complexity for the second part is O(m). For the last part, the complexity depends on the total number of updating operations of loss values, which is calculated as ∑v∈C+ deg(v) < ∑v∈V deg(v) = 2m. Therefore, the ConstructVC procedure has a complexity of O(m), which is lower than O(n2 ) in most cases. Especially, most massive real world graphs are sparse graphs [Barabási and Albert, 1999; Eubank et al., 2004; Lu and Chung, 2006], and heuristics with O(m) complexity are much faster than those with O(n2 ) for such graphs.

4.2 Best fromMultiple Selections (BMS)

A critical function of FastVC is ChooseRmV ertex, which returns a vertex from the candidate vertex set C to remove. We propose a fast and effective heuristic for doing this task, which strikes a good balance between the time complexity and the quality of the selected vertex (w.r.t. the loss value).

Local search algorithms usually need to select an element from a candidate set. Perhaps the most commonly used strategy is to choose the best element according to some criterion, which we refer to as "best-picking" heuristic. With a suitable criterion, this heuristic guides the search towards the most promising area, and is thus widely adopted in local search algorithms. Recent examples of such heuristics for MinVC include the max-gain pair selection heuristic in COVER [Richter et al., 2007] and the minimum loss removing heuristic in NuMVC [Cai et al., 2013]. More examples can be found in local search algorithms for other famous NP-hard problems, such as the Satisfiability problem [Selman et al., 1992; Hoos and Stützle, 2004; Li and Huang, 2005; Cai and Su, 2013]. Indeed, a lot of works on local search have been focused on the criterion for filtering the candidate set and the function for comparing elements, and once this is done, they simply pick the best one. The "bestpicking" heuristic works well in most cases, but not for massive data sets where the candidate set is usually very large and finding the best element is very time-consuming.

We propose a cost-effective heuristic called Best from Multiple Selections (BMS), for picking a good element from a set, and we use it for the ChooseRmV ertex function. For a set S, the BMS heuristic works as follows:

Choose k elements randomly with replacement from the set S, and then return the best one (w.r.t. some comparison function f), where k is a parameter.

A more formal description of the BMS heuristic is given in Algorithm 3. Let us look at how well the BMS heuristic approximates the "best-picking" heuristic. For a real number ρ ∈ (0, 1), the probability of the event E = {the f value of the element chosen by BMS is not greater than ρ|S| elements Algorithm 3: Best from Multiple Selection (BMS) Heuristic

Input: A set S, a parameter k, a comparison function f //assume f is a function such that we say an element is better than another one if it has smaller f value Output: an element of S best :=a random element from S; 1 for iteration := 1 to k - 1 do 2 r :=a random element from S; 3 if f(r) < f(best) then best := r; 4 return best; 5

in the set S} is P r(E) ≥ 1-( ρ|S|-1 |S| )k > 1-ρk (the first "≥" because there might be the case that more than one elements in those ρ|S| elements have the same f value, which is the minimum among f values of all the ρ|S| elements).

For ChooseRmV ertex, the comparison function f is simply the loss function on vertices, and we set k = 50. Then, the probability that the BMS heuristic chooses a vertex whose loss value is not greater than 90% vertices in C is Pr(E) > 1 - 0.950 > 0.9948. The above calculations illustrate that the BMS heuristic returns a vertex of very good quality with a very high probability.

The complexity of the BMS heuristic is O(k) = O(1), since k is a constant parameter. This is lower than O(|C|) for the minimum loss heuristic used by previous local search algorithms for MinVC. Note that BMS is a generic heuristic and can be also applied to improve the time efficiency of local search algorithms for large scale instances of other problems.

5 Experimental Evaluation

In this section, we carry out extensive experiments to evaluate FastVC on a broad range of real world graphs, compared against the state of the art local search MinVC algorithm NuMVC.

5.1 Benchmarks

For our experiments, we collected all undirected simple graphs (not including DIMACS and BHOSLIB graphs) we could find from the Network Data Repository online [Rossi and Ahmed, 2015]. 3 Many of these real world graphs have millions of vertices and dozens of millions of edges. Some of these benchmarks have recently been used in testing parallel algorithms for Maximum Clique and Coloring problems [Rossi and Ahmed, 2014; Rossi et al., 2014].

The graphs in our experiments can be grouped into 10 classes, including biological networks, collaboration networks, facebook networks, interaction networks, infrastructure networks, amazon recommend networks, scientific computation networks, social networks, technological networks, and web lint networks, in the order of their appearance in the tables. There is also a group of temporal reachability networks, where the graphs are small (usually with several hundreds or several thousands of vertices) and the two algorithms find the same quality solution on all the graphs, and thus is not included in our experiment.

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

5.2 Experiment Setup

For comparisons, we use the NuMVC algorithm [Cai et al., 2013] to represent the state of the art in solving MinVC (and also MaxIS) problem. Based on experiments on DIMACS and BHOSLIB benchmarks, NuMVC succeeds more reliably to find the optimal or best known solution at speeds at least several times faster than earlier MinVC and MaxIS algorithms [Cai et al., 2013]. It is acknowledged as the latest breakthrough for MinVC solving in the literature [Fang et al., 2014; Rosin, 2014; Jin and Hao, 2015]. Slightly better results have been reported for two algorithms that build on the top of NuMVC [Fang et al., 2014; Cai et al., 2015], but this does not materially change our conclusions below.

We implement our algorithm FastVC in the C++ programming language. NuMVC is open-source and also implemented in C++. 4 Both algorithms are complied by g++ (version 4.4.5) with the '-O3' option. For NuMVC, we adopt the parameter setting reported in [Cai et al., 2013]. For the BMS heuristic in the ChooseRmV ertex function of FastVC, we set the k parameter to 50, as mentioned in the previous section. The experiments are carried out on a workstation under Ubuntu Linux, using 2 cores of i74800MQ 2.7 GHz CPU and 8 GByte RAM.

Both algorithm are executed 10 times on each instance with a time limit of 1000 seconds. For each algorithm on each instance, we report the minimum size ("Cmin") and averaged size ("Cavg") of vertex covers found by the algorithm. To make the comparison clearer, we also report the difference ("∆") between the minimum size of vertex cover found by NuMVC and that found by FastVC. A positive ∆ means FastVC finds a smaller vertex cover, and a negative ∆ means NuMVC finds a smaller vertex cover. For some instances, NuMVC fails to find a vertex cover within the time limit, then the column for NuMVC is marked as "n/a" and the "∆" column is marked as "max" (since FastVC finds one).

5.3 Experiment Results

We present the main experiment results in Tables 1 and 2. For the sake of space, we do not report the results on graphs with less than 1000 vertices, for which both algorithms find the same quality solutions quickly. Also, three extremely large graphs are not reported as they are out of memory for both algorithms.

From the results in Tables 1 and 2, we observe that:

1. Out of the 86 graphs, FastVC finds better vertex covers than NuMVC for 46 graphs, and finds the same quality solutions for 37 graphs. FastVC finds worse solutions only for 3 graphs.
2. The two algorithms have similar performance on two classes of benchmarks, namely the biological networks and interaction networks; for other classes of benchmarks, FastVC significantly outperforms NuMVC.
3. There are 10 graphs for which NuMVC fails to provide a vertex cover within the time limit, while FastVC finds vertex covers for all the graphs. This indicates the effectiveness of our construction heuristic. In fact, further observations show

4 http://lcs.ios.ac.cn/~caisw/Code/NuMVC-Code.zip

that the construction heuristic in FastVC outputs a vertex cover typically in one second.

4) The ∆ value is greater than 10 for 30 graphs. Such big improvements on the size of vertex cover are very exciting, when compared to those in the literature of MinVC algorithms.

For 33 graphs where the two algorithms consistently find vertex covers of the same size, we compare their averaged running time to locate such a solution. The results are reported in Table 3, which show that FastVC is much faster than NuMVC.

6 Summary and FutureWork

In this work, we develop a local search algorithm for MinVC called FastVC, based on two new heuristics. The first heuristic is a construction procedure which has a complexity of O(|E|), compared to O(|V |2 ) for the construction heuristic used in previous local search algorithms for MinVC. The second one is the Best from Multiple Selections (BMS) heuristic, which approximates the minimum loss heuristic very well and lowers the complexity from O(|V |) to O(1).

Thanks to these two heuristics, the FastVC algorithm performs much better than the state of the art algorithm NuMVC on massive graphs. Experiments on massive real world graphs show that, FastVC finds smaller vertex covers than NuMVC on most graphs. Also, FastVC finds a "good" (or at least not too bad) vertex cover for all the graphs within reasonable time (1000 seconds), while NuMVC fails to find a vertex cover on a considerable portion of the graphs.

This work takes a first step towards local search for MinVC on massive graphs, and also provides key insights about balance between complexity and quality of heuristics for massive data problems. In the future, we would like to design more efficient heuristic algorithms for MinVC as well as other graph problems on massive graphs.

Acknowledgement

This work is supported by China National 973 Program 2014CB340301, National Natural Science Foundation of China 61370072, 61370156 and 61472369. We would like to thank the anonymous referees for their helpful comments.