Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies

1 Introduction

The minimum weight vertex cover problem (MWVC), an extension of the minimum vertex cover problem (MVC), is a well-known combinatorial optimization problem. Given a graph G, a vertex cover is a subset of vertices that contains at least one incident vertex of each edge. The MVC problem is to find a vertex cover with the minimum size. When extended to MWVC, each vertex in G has a positive weight, and the task is to find a vertex cover with the smallest total weight. The MWVC problem has been applied to various real-world problems. In particular, with the rise of dynamic digital maps, the dynamic map labeling problem has attracted more and more attention [Been et al., 2006; 2010; Liao et al., 2016; Barth et al., 2016]. This problem can be naturally encoded as the MaximumWeight Independent Set problem (MWIS), and can also be directly solved by MWVC algorithms, as vertex cover and independent set are two complementary concepts in graphs.

∗Corresponding author

MVC is an NP-hard problem. Moreover, it is NP-hard to be approximated within any factor smaller than 1.3606 [Dinur and Safra, 2005]. Therefore, it is generally not efficiently solvable. Most studies on MVC focus on heuristic algorithms, which return solutions of acceptable quality in reasonable time. Heuristic MVC algorithms are usually based on local search, including the widely acknowledged state of the art algorithm NuMVC [Cai et al., 2013]. Recently, there is increasing interest in solving MVC on massive graphs. Since the introduction of FastVC [Cai, 2015], several local search algorithms have been proposed for solving MVC on massive graphs, and the latest state of the art is established by improved versions of FastVC [Cai et al., 2017].

Most studies on solving MWVC are devoted to heuristic algorithms to find near-optimal solutions in reasonable time. The ideas used in these algorithms include ant colony [Shyu et al., 2004; Tuba and Jovanovic, 2009; Jovanovic and Tuba, 2011], simulated annealing [Voß and Fink, 2012] and asymmetric game [Tang et al., 2017]. A tabu search algorithm named Multi-Start Iterated Tabu Search (MS-ITS) [Zhou et al., 2016] achieved state-of-the-art performance on a broad range of small and middle sized benchmarks. As for solving MWVC on massive graphs, two recent local search algorithms DLSWCC [Li et al., 2016] and FastWVC [Li et al., 2017] made significant improvements, where FastWVC performs better.

MWVC are related to Maximum Weight Clique Problem (MWCP) on the complementary graphs. Recently, there has been significant progress in solving MWCP on sparse massive graphs [Wang et al., 2016; Cai and Lin, 2016; Jiang et al., 2017]. But these algorithms may not be efficient to find an MWVC in these graphs, because finding the MWVC is equivalent to finding the MWC in the very dense complement graphs, which also motivates dedicated approaches for MWVC.

Although it is interesting to evaluate MWVC algorithms on massive graphs, a drawback of the current evaluations of MWVC algorithms is that the weights are hand crafted or randomly generated, and do not have real meanings in applications. Indeed, this drawback has been pointed out in evaluations of MWCP algorithms [McCreesh et al., 2017]. It is more desirable to evaluate MWVC algorithms on real application benchmarks, where both the graphs and weights are transferred from real world problems. In this work, we evaluate our algorithms on instances arisen from the map labeling problem - an important problem in digital maps. To show the robustness of our algorithms, we also evaluate them on massive sparse graphs used in previous works.

Our algorithm is built upon a baseline local search algorithm that is abstracted and modified from FastWVC [Li et al., 2017], which maintains the validity of the candidate solution at the end of each iteration. To improve the algorithm, we propose two dynamic strategies, both of which are used in choosing vertex to be removed. The first one combines two heuristics that use different scoring functions. This is different from previous algorithms, which use only one scoring function during the search. The cooperation of the two heuristics are controlled by a parameter that counts the number of non-improving steps w.r.t. solution quality. By using this dynamic strategy, we develop a new local search algorithm named DynWVC1. Experiments show that DynWVC1 outperforms previous heuristic MWVC algorithms on both map labeling graphs and massive graphs.

The second idea is a dynamic strategy for deciding the number of removed vertices. Previous studies mainly remove one vertex in the removing phase of each local search step, FastWVC suggests to remove two vertices. This strategy produces more uncovered edges and thus makes the search region larger. As it turns out, this two-removal strategy has a significant contribution to the good performance of FastWVC. However, the degrees of vertices vary a lot, and removing two vertices might still be not sufficient if the two selected vertices have small degrees. We suggest to remove one more vertex if the total degree of the two removed vertices is not large enough. This idea is related to ideas of exploring large neighborhoods, including k-swap in local search for unweighted vertex cover [Katzmann and Komusiewicz, 2017], and (k - 1, k)-swap for unweighted independent set [Andrade et al., 2012]. However, in our strategy, this is decided dynamically, according to a criterion on the total degree of removed vertices. We improve DynWVC1 using this strategy, leading to the DynWVC2 algorithm. DynWVC2 further improves DynWVC1 on massive sparse graphs and is currently the best MWVC algorithm on these sparse graphs.

The reminder of this paper is organized as follows. Section 2 presents basic definitions. Section 3 presents the baseline algorithm. Section 4 introduces the dynamic strategy that combines two heuristics to choose vertex to remove, as well as the DynWVC1 algorithm. Section 5 explains the dynamic strategy that determines the number of vertices to remove, and presents the DynWVC2 algorithm. Experiment results are shown in Section 6. Section 7 gives concluding remarks.

2 Preliminaries

2.1 Basic Definitions and Notation

For a weighted graph G = (V,E), V is the set of vertices, E is the set of edges, and each vertex v ∈ V has a positive weight w(v). Each edge consists of two vertices, which are called endpoints of the edge. Two vertices are neighbors if they belong to the same edge, N(v) = {u ∈ V |(u, v) ∈ E} is the set of neighbors of v, and degree(v) = |N(v)|. For a vertex set S, N(S) = ⋃v∈S N(v).

A candidate solution is a subset of V. An edge is covered by a candidate solution if at least one of its endpoints belongs to it. The current candidate solution is denoted as C, and we use w(C) to denote the total weight of vertices in C. Further, we use sv = {1, 0} to denote the state of a vertex. If v ∈ C, then sv = 1, and we call v a covering vertex. If v /∈ C, then sv = 0 and we call v an uncovering vertex. The age of a vertex, denoted as age(v), is the number of steps that have happened since v last changed its state.

A vertex cover of a graph is a subset of V that covers all edges, 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. The MWVC problem is to find a vertex cover C ∗ such that w(C ∗ ) is minimum, which is equivalent to the Maximum Weight Independent Set (MWIS) problem, i.e., seeking for an independent set with the largest weight.

2.2 Scoring Functions

As with most local search algorithms for MVC and MWVC, our algorithms also use an edge weighting mechanism. Each edge e ∈ E is associated with a positive number edge w(e) as its weight. The cost of C, denoted by cost(C), is the total weight of edges uncovered by C.

The change of cost caused by changing the state of a vertex v is denoted as dscore(v), i.e.,

where C ′ is the candidate solution after changing the state of v, that is, if v ∈ C, C ′ = C\{v}, otherwise C ′ = C ∪ {v}. We have dscore(v) ⩾ 0 if v /∈ C and dscore(v) ⩽ 0 if v ∈ C.

Two scoring functions gain and loss are used to measure how much contribution (or damage) a vertex will make to the solution by changing its state, considering both edge weighting mechanism and vertex weights. They are formally defined as

Most local search algorithms for MWVC keep the candidate solution valid at the end of each step. Suppose in a step, a vertex v is removed, making some edges uncovered, then some vertices are added to cover those edges to keep the candidate solution valid. Based on this observation, a scoring function for vertices in C is as follows [Zhou et al., 2016].

where Vr(v) denotes the set of adjacent uncovering vertices of v.

The BMS (Best fromMultiple Selection) heuristic is used to choose a good-quality element from a large set [Cai, 2015]. It randomly picks k elements and returns the best one w.r.t. some criterion. Our algorithms utilize the BMS heuristic, and parameter k is always set to 50, which guarantees the returned vertex is among the top 10%w.r.t. the criterion with a probability greater than 0.99, as proved in [Cai, 2015].

2.3 Map Labeling Problem

Map labeling is a research area in cartography and computational geometry. Components in a graph such as geographic places and points of interests should be labeled in order to be meaningful to the users. Map labeling involves the selection and placement of labels in maps and one constraint is that two labels should not overlap each other. The problem of eliminating label conflicts and maximizing the importance of labels displayed can be modeled as the Maximum Weight Independent Set (MWIS) problem [Barth et al., 2016]. More specifically, for static graphs, each label can be viewed as a vertex, each vertex is assigned a weight based on its importance, there is an edge between two vertices if they overlap each other. For dynamic graphs, the set of labels displayed changes over time based on operations such as zooming, panning and rotating. Therefore, [a, b]l, which denotes label l displays in time interval [a, b], is viewed as a vertex, each vertex is assigned a weight based on the weight of its label and the length of its time interval. Two vertices are connected by an edge if they conflict with each other. The purpose of maximizing the overall display time of labels can be viewed as finding an independent set that has the maximum weight, which is equal to finding a vertex cover with the minimum weight.

3 Baseline Algorithm

In this section, we introduce a baseline algorithm. We propose a local search framework for MWVC, and then present the important heuristics adopted in our baseline algorithm.

3.1 ANew Local Search Framework for MWVC

We introduce a local search algorithmic framework for MWVC (Algorithm 1). This framework is abstracted from FastWVC and is modified to make it more efficient.

An initial vertex cover C is firstly generated by a procedure Construct. Then the algorithm enters the local search process. Each step consists of a removing phase and an adding phase. In removing phase, vertices are removed by the RemoveVertices function (line 5). In adding phase, vertices are added to C until it becomes a vertex cover again. After that, redundant vertices are detected and removed (line 10). If the newly found solution C is better than the best found solution C ∗ , C ∗ is updated to C. At the end of the algorithm, C ∗ is returned.

A remark on the way to add vertices: All uncovered edges are incident to at least one removed vertex in the removing phase of this step. So, in order to make C valid again, the vertices to be added must be in the set N(R), where R is the set of removed vertices in this step. In our algorithm, adding vertices are selected from N(R).

Input: A vertex weighted graph, the cutoff time Output: A vertex cover of G 1 begin 2 C ←Construct(); 3 C∗ ←C; 4 while elapsed time < cutoff do 5 RemoveV ertices(C); 6 R←{the vertices removed in this step}; 7 while some edge is uncovered by C do 8 choose a vertex v from N(R); 9 C ← C ∪ {v}; 10 remove redundant vertices fromC; 11 if w(C) < w(C∗ ) then C∗ ← C; 12 return C∗ ;

3.2 Construct Function

Our baseline algorithm employs the construct function in FastWVC. Specifically, the function consists of two phases: a repeated extending phase and a shrinking phase. The extending phase generates k vertex covers and returns the best one according to BMS heuristic. Each vertex cover is constructed by scanning an uncovered edge each time and adding the endpoint with the greater gain value. Different random scanning orders are used so that the k vertex covers are different, and the best one among them is handed to the shrinking phase, where redundant vertices are removed.

3.3 RemoveVertices Function

Another important function in the local search framework is the RemoveVertices function. For our baseline algorithm, we adopt the one in FastWVC. Two vertices are removed. Firstly, a vertex with the minimum loss value is selected and removed from C. Then, the second vertex to remove is selected by using the BMS heuristic w.r.t. the loss value.

4 DynWVC1 Algorithm

We propose two dynamic strategies to improve the baseline algorithm, both strategies focus on the RemoveVertices function. This section presents the first strategy, as well as the resulting algorithm improved by it (called DynWVC1).

4.1 Choosing Scoring Functions Dynamically

Vertex selection heuristic is critical in local search algorithms for MWVC. To select vertices to remove from C, various scoring functions have been proposed. Two effective scoring functions are loss and valid score introduced in Section 2.

The loss and valid score functions have essentially different impact on the behavior of the algorithm. Vertex selection using loss function is an "exploratory" selection; in other words, there is a good chance that such a selected vertex is good for solution quality, but we can not be certain of that. Different from "exploratory" vertex selection, valid score is a "deterministic" one, that is, we can know exactly whether the removal of a vertex will have a positive effect on solution quality. For example, if the valid score value of a vertex is negative, it means that, if we remove this vertex and add

Algorithm 2: DynamicChoose(no improve, α)

Input: parameter no improve and α Output: a vertex to be removed 1 begin 2 if no improve < α then 3 choose a vertex u with minimum valid score from C, breaking ties in favor of the oldest one; 4 else 5 choose a vertex u with small loss from C according to BMS strategy,breaking ties in favor of the oldest one; 6 no improve ← 0; 7 return u;

its adjacent uncovering vertices, we can get a vertex cover with lower cost than the current one. However, just like other deterministic heuristics, local search using valid score alone easily gets trapped in local optima.

We propose a dynamic vertex selection strategy, which consists of a primary vertex scoring function and a secondary scoring function. The primary function is valid score and the secondary is loss. We put the implementation of this strategy into a function called DynamicChoose (Algorithm 2), which is used to select the second removing vertex. The parameter no improve denotes the number of iterations in which the valid score function fails to decrease the weight of vertex cover. If no improve is smaller than a predetermined parameter α, a vertex with the smallest valid score will be removed; if no improve achieves α, which means valid score loses its effectiveness for a good number of steps, then the secondary function loss is activated to pick the vertex according to BMS heuristic, in the same way as FastWVC. In both cases, ties are broken by preferring the oldest vertex.

The no improve is initialized as 0 at the beginning of the algorithm. When the solution found in this iteration is no better than the solution in last iteration, it shows that the removing vertex selected by valid score does not contribute well to the solution quality, then no improve is increased by 1. Each time using the secondary function, no improve is reset to 0, so that DynamicChoose switches back to the main scoring function.

The intuition of this strategy is to make valid score and loss complement each other. The valid score chooses the most valuable removed vertex in the current step, and when it loses effectiveness, the loss function guides the search to a new area and creates more valuable vertices for valid score to select.

4.2 Description of DynWVC1 Algorithm

We use the DynamicChoose function to improve the baseline algorithm, leading to a local search algorithm named DynWVC1 (Algorithm 3). In the beginning, the initial vertex cover C is generated by the construct function as shown in the baseline algorithm. Edge weights are all initialized as 1. Then, gain of vertices in V \ C, loss and valid score of vertices in C are calculated. Parameter no improve is set to 0. We use C ∗ and C ′ to denote the best found solution and the solution found in last iteration of local search.

In the main loop, each iteration consists of a removing

Algorithm 3: DynWVC1

Input: A weighted graph G = (V, E, W), cutoff, α Output: A vertex cover of G 1 begin 2 C ←Construct(); 3 C∗ ,C′ ←C; 4 for each e ∈ E, edge w(e) ← 1; 5 calculate gain, loss and valid score of vertices; 6 no improve ← 0; 7 while elapsed time < cutoff do 8 choose a vertex w with minimum loss from C, breaking ties in favor of the oldest one; 9 C ← C \ {w}; 10 u ←DynamicChoose(no improve, α); 11 C ← C \ {u}; 12 R ← {w, u}; 13 while some edge is uncovered by C do 14 choose a vertex v with maximum gain from N(R), breaking ties in favor of the oldest one; 15 C ← C ∪ {v}; 16 edge w(e) ← edge w(e) + 1 for each uncovered edge; 17 remove redundant vertices fromC; 18 if w(C) < w(C∗ ) then C∗ ← C; 19 if w(C′ ) ≤ w(C) then no improve++; 20 C′ ←C; 21 return C∗ ;

phase and an adding phase. In the removing phase, two vertices are removed from C. Firstly, a vertex w with the minimum loss is first removed from C. Then, the second vertex u is selected by DynamicChoose function introduced in Section 4.1. After the removal of w and u, some of their incident edges may become uncovered.

In the adding phase, vertices are added into C until C becomes a vertex cover. As explained in the baseline algorithm, we only need to consider the vertices in N(R) = N(w)∪N(u). Specifically, while C is not yet a vertex cover, a vertex v ∈ N(R) with the maximum gain is chosen and added to C, breaking ties by preferring the oldest one (line 14-15). Then weights of all uncovered edges are increased by 1. At the end of each adding operation, redundant vertices whose neighbors are all covering vertices are removed. Note that this is different from previous algorithms, which remove redundant vertices by scanning all vertices in C after all adding operations are done. In fact, only neighbors of the adding vertex may become redundant vertices, and thus we only need to check the neighbors of the vertex just added.

If C is better than C ∗ , C ∗ is updated to C. If the solution found in this step is no better than the solution in last step, i.e., C is no better than C ′ , no improve is increased by 1. Finally, C ′ is set to C. At the end of the algorithm, the best found solution C ∗ is returned.

5 DynWVC2 Algorithm

In most local search algorithms for MVC and MWVC, one vertex is removed in the removing phase, FastWVC [Li et al., 2017] proposes to remove two vertices at one iteration to enlarge the search region. It is an effective strategy especially for massive sparse graphs. However, the degrees of vertices vary a lot, the search region produced by removing two vertices is not always sufficient for the search process. From the overall point of view, removing two vertices is an effective method. But from the view of each step, the search region produced by it may be still not enough for some steps.

To make the algorithm more efficient on massive sparse graphs, we incorporate a new strategy into DynWVC1 for deciding the number of removed vertices, resulting in the DynWVC2 algorithm. In DynWVC2, the first two removing vertices are selected and removed in the same way as DynWVC1. After removing two vertices, if the total degree of the removed vertices does not reach a predetermined value (which is set to 2 times average degree of the graph), then the algorithm removes one more vertex with small loss based on BMS strategy. In this way, when the search region produced by removing two vertices is too small, which limits our options in the adding phase, it can be expanded by removing one more vertex. If the search region produced by removing two vertices is large enough, to get a balance between search time and search quality, we do not remove the third one.

6 Experiments

We evaluate our algorithms on map labeling instances and massive graphs, compared with state of the art algorithms.

6.1 Experiment Preliminaries

Setup: DynWVC1 and DynWVC2 are implemented in C++, and compiled by g++ with '-O3' option. The parameter in our algorithms α is set to 5. All experiments are run on a 4-way Intel Xeon E7-8850 v2 @ 2.30GHz CPU with 1TB RAM server under CentOS 7.2.

Competitors: For the map labeling benchmark, we compare with three local search algorithms for MWVC namely MS-ITS [Zhou et al., 2016], DLSWCC [Li et al., 2016] and FastWVC [Li et al., 2017], and a local search algorithm for MWIS namely PLS MWIS [Pullan, 2009], which is selected as the best MWIS algorithm for the map labeling benchmark [Barth et al., 2016]. For the massive graphs, FastWVC performs significantly better than MS-ITS and DLSWCC [Li et al., 2017], so we only compare with FastWVC. All competitors are implemented by their authors using C++ and complied by g++ with '-O3' option.

Results Reporting Methodology: All algorithms are executed 10 times on each instance independently with a cutoff time of 1000 seconds. We report the following information: the average weight of the solutions found in 10 runs ("wavg"), the best solution found in 10 runs. For map labeling, we treat it as MWIS problem, and report the weight of independent set (the larger the better). For massive graphs MWVC instances, the smaller weight the better. If an algorithm failed to find a solution within time limit, we marked it by "N/A".

6.2 Experiments onMap Labeling Benchmark

We download the map files for North America from OpenStreetMap 1 and generate conflict graphs from them using the software 2 developed by Barth et al. [Barth et al., 2016], which are used as the benchmark. We consider almost all the POIs 3 to label during the generating procedure. For each map file, there are three resulting conflict graphs corresponding to the Activity Model chosen, namely AM1, AM2 and AM3 [Barth et al., 2016]. We do not report results on instances with fewer than 1000 vertices, which are easy to solve.

Experiment results on these instances are shown in Table 1. DynWVC1 finds better solutions than other algorithms on most instances. Also, DynWVC1 is much faster than other algorithms: its average run time is 219s, while this figure is 498s for PLS WIS, 593s for MS-ITS, 329s for DLSWCC and 443 for FastWVC. Also, DynWVC2 has almost the same performance as DynWVC1, and is not reported.

6.3 Experiments onMassive Graphs

We also evaluate our algorithms on massive graphs from Network Data Repository [Rossi and Ahmed, 2015]. Many of them have 100 thousands to millions of vertices, and dozens of millions of edges. These instances become popular in recent heuristic works for MWVC. The weight of each vertex is assigned to a value from [20,100] uniformly at random, as adopted in testing DLSWCC and FastWVC [Li et al., 2017].

1 http://download.geofabrik.de/north-america.html

2 https://github.com/kit-algo/temporalmaplabeling

3 https://wiki.openstreetmap.org/wiki/Map Features

Table 2 reports results on massive graphs with more than 10,000 vertices. DynWVC1 and DynWVC2 find better solutions than FastWVC on most instances, pushing forward the state of the art in solving MWVC for massive sparse graphs. Additionally, DynWVC2 improves DynWVC1 on these instances. For 37 out of 73 instances, DynWVC2 has better performance than DynWVC1 in terms of both best and averaged solution quality, while DynWVC1 has better performance on 14 instances. For the remained instances, neither of them dominates on both measurements.

6.4 Effectiveness of DynamicChoose

To study the effectiveness of the dynamic strategy for choosing scoring function, we compare DynWVC1 with its simplified version that does not use the DynamicChoose function, namely SimpWVC. We report the difference between the best solutions and difference between averaged solutions found by DynWVC1 and SimpWVC. We only present results on map labeling instances with more than 1000 vertices and massive graphs with more than 10000 vertices. Experiment results are shown in Table 3 and 4, respectively. Almost all ∆ values are negative, indicating that DynWVC1 finds better solutions than SimpWVC on almost all instances. We conclude that the DynamicChoose function effectively improves the algorithm.

7 Conclusions and FutureWork

This paper focused on efficient heuristic algorithms for MWVC. We introduced a local search framework, and proposed two dynamic strategies to improve the baseline algorithm, leading to two local search algorithms for MWVC.

We evaluated our algorithms on the instances transferred from the real world map labeling problems and massive sparse graphs. Our algorithms significantly outperform previous heuristic algorithms. We would like to improve our algorithms for more real world problems.