Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game

Jie Chen,Kaiyi Luo,Changbing Tang,,Zhao Zhang,,and Xiang Li, Senior

Abstract—Weighted vertex cover (WVC) is one of the most important combinatorial optimization problems.In this paper,we provide a new game optimization to achieve efficiency and time of solutions for the WVC problem of weighted networks.We first model the WVC problem as a general game on weighted networks.Under the framework of a game,we new ly define several cover states to describe the WVC problem.Moreover,we reveal the relationship among these cover states of the weighted network and the strict Nash equilibriums (SNEs) of the game.Then,we propose a game-based asynchronous algorithm(GAA),which can theoretically guarantee that all cover states of vertices converging in an SNE with polynomial time.Subsequently,we improve the GAA by adding 2-hop and 3-hop adjustment mechanisms,termed the improved game-based asynchronous algorithm(IGAA),in which we prove that it can obtain a better solution to the WVC problemthan using a the GAA.Finally,numerical simulations demonstrate that the proposed IGAA can obtain a better approximate solution in promising computation time compared with the existing representative algorithms.

I.INTRODUCTION

IN recent years,there has been a growing interest in the controlling and monitoring of autonomous intelligent systems[1]–[8],data gathering in the internet of things [9]–[13],etc.Consider the efficient transmission of information where a set of agents is marked,from which all the information collected by the marked agents could be accessible with minimum cost.In particular,when each agent is heterogeneous,the above problem can be regarded as the weighted vertex cover (WVC)problem.Note that the WVC problem degrades into the socalled vertex cover problem when the vertices have equal weight.In fact,the WVC problem is a generalized type of the vertex cover problem,which is aimed at finding a minimum weighted set of network “covered”vertices covering all edges of the network [14].The WVC problem has also been found to have other applications in wireless sensor networks [1],network security [15],computational biology [16],etc.

Since the WVC problem is a nondeterministic polynomial(NP) hard problem,this implies that an exact solution can not be obtained in a polynomial time,unless P=NP [17].In order to solve the (weighted) vertex cover problem,many researchers developed approximation algorithms,such as polynomial time algorithms [18]–[20],branch-and-bound search algorithms [21],quantum algorithms [22],evolutionary algorithms [23],and approximate algorithms [24],[25],etc.Although these algorithms have achieved good results with regards to efficiency,they are centralized.That is,there exists a central controller that controls the whole decision process.In a large-scale network system,such a requirement is difficult to satisfy.

Fortunately,such shortcomings can be addressed within a distributed framework.With distributed algorithms,each agent makes decisions in response to local information.Game theory is suitable for such an autonomous requirement,which emerges as a powerful tool for distributed optimization[26]–[31].Note that two aspects should be considered when applying game theory.First,it is common to treat each vertex as a player and model the interaction framework of players within a game theoretic environment (game design),in which a set of strategies and a local utility function for each player is defined.Second,applying game theory involves specifying a game-based distributed algorithm that enables the strategies of all players to reach a desirable state,termed a (strict) Nash equilibrium.One of the core advantages of using game theory for a distributed system,is that it provides a hierarchical decomposition between the design of the interaction framework and the design of the game-based distributed algorithm[32].

A t present,some researchers have designed or applied various game models to describe the (weighted) vertex cover problem,and proposed many efficient algorithms to obtain feasible solutions [33]–[36].Yang and Li [33] applied a snowdrift game model framework to describe the vertex cover problem of networks and proposed a memory-based best response (MBR) algorithm.Recently,Chen and Li [34] proposed a time variant binary log-linear learning algorithm for the vertex cover problem of networks,which can theoretically converge to the minimum vertex cover state in infinite time.In the case of weighted networks,Tanget al.[35] established an asymmetric game model to describe the WVC problem of weighted networks,in which they found a better approximate solution for the WVC problemunder using the feedback based best response algorithm.Subsequently,Sunet al.[36]established a potential game model to describe the WVC problem of weighted networks,and proposed a distributed relaxed greedy and memory-based algorithm.

Although such works have achieved good results in solving the WVC problem,the aforementioned efforts are not sufficient towards completely understanding the WVC problem on networks.On one hand,the algorithms in [35],[36] can converge to an strict Nash equilibrium(SNE),which only satisfies the local minimum weighted vertex cover (LMWVC)state.This inspires us to further study the SNE of network weighted vertex cover game,which is related to the global minimum weighted vertex cover (GMWVC) state.On the other hand,numerical experiments show that the algorithms can obtain a better SNE by increasing the memory length,but an increased computing time is needed [35],[36].This shortcoming results in a challenge: Determining how to develop a more efficient algorithmthat can arrive at a desired solution with promising computation time.

In this paper,we establish a general game model for the WVC problem,and explore the relationship between several cover states (such as LMWVC,GMWVC) and the SNEs of the game.Compared with the SNEs of the existing game model [35],[36],we redefine the SNE of the network weighted vertex cover game,which can narrow the scope of searching for the optimal solution for the WVC problem.Then,we design a new algorithm,i.e.,game-based asynchronous algorithm(GAA),which can arrive at an SNE in polynomial time.Unfortunately,the GAA can only find SNE within memory length 1,which makes it easy to fall into an inefficient solution.To improve efficiency of the solution,we further improve the GAA and propose an improved game based asynchronous algorithm(IGAA).We can then obtain a more efficient solution with promising computation time with memory lengthm≥1.The main contributions are summarized as follows.

1) Description of Cover States:We establish a novel general game model for the WVC problem.Under the framework of the game,we define three cover states to describe the WVC problem,where we can narrow the scope of searching for the optimal solution for the WVC problem.Moreover,we reveal the relationship between the cover states of a weighted network and the SNEs of the established game model.

2) Convergence Time of Solution:We propose a algorithm with memory lengthm=1,i.e.,GAA.The theoretical analysis shows that the GAA can obtain an SNE in polynomial time.

3) Efficiency of Solution:By adding thel-hop(l=2,3)adjustment mechanism into the GAA,we propose a novel IGAA with memory lengthm≥1,which can guarantee that strategies of all players converge to an SNE.In particular,whenm=1,the IGAA can obtain a better solution for the WVC problem than that of the GAA.

4) Verification of Simulation:By comparing with existing typical algorithms,numerical results illustrate that the proposed IGAA can obtain a better approximate solution in promising computation time.

The rest of this paper is organized as follows.In Section II,we introduce the preliminaries.In Section III,we establish a game model for the WVC problem.Section IV analyzes the relationship between several cover states and the SNEs.In Section V,we propose two asynchronous algorithms,i.e.,GAA and IGAA,and analyze their convergence theoretically.In Section VI,we provide numerical examples to illustrate empirical performance of the proposed IGAA.Conclusions are discussed in Section VII.

II.PRELIMINARIES

In order to better characterize the WVC problem,we define several cover states as follows.

Definition 1:An undirected weighted graphGsatisfies the WVC state,if the setVWVChas the global minimum total covered weight,then the set is called a GMWVC set (denoted it asVGMWVC).In this case,graphGsatisfies the GMWVC state.

Definition 2:An undirected weighted graphGsatisfies the WVC state,if any covered vertex in setVWVCbecomes an uncovered vertex,and graphGno longer satisfies the WVC state,then the set is called a local minimum weighted vertex cover set (denoted it asVLMWVC).In this case,graphGsatisfies the LMWVC state.

Definition 3:An undirected weighted graphGsatisfies the WVC state,if any covered vertex in graphGbecomes an uncovered vertex with all neighbors becoming covered vertices,and the total covered weight of the graphGdoes not decrease,then the network satisfies the Nash cover equilibrium(NCE) state.The covered vertices of the graphGcan for man NCE set (denoted it asVNCE).

We illustrate all four cover states in Fig.1.Note that Figs.1(a)?1(d) satisfy the WVC state,and their total cover weights are 13,12,10,and 9,respectively.In Fig.1(b),if any covered vertex becomes an uncovered vertex,then Fig.1(b)no longer satisfies the WVC state.According to Definition 2,Fig.1(b) satisfies the LMWVC state.Similarly,according to Definition 3,we verify that Fig.1(c) satisfies the NCE state.Moreover,it is easy to check that the minimumtotal cover weight of Fig.1(d) is 9,which results in Fig.1(d) satisfying the GMWVC state.Note that the LMWVC and the NCE states are local definitions,while the GMWVC state is a global definition.Conveniently,we summarize the notations in Table I.

Fig.1.Black nodes are covered vertices,and white nodes are uncovered vertices (the same as following figures).Numbers in nodes indicate vertex weights.(a) WVC state;(b) LMWVC state;(c) NCE state;(d) GMWVC state.

III.GAME MODEL

For two players,the one with a larger weight is said to be the stronger player,and the other is said to be the weaker player.When two players have the same weight,we regard themas stronger players,or weaker players.The stronger(weaker) player who chooses the strategyz(z∈A) is denotedasS Pz(W Pz).In [35],the authors proposed an asymmetric game,in which the degree of asymmetry is designed artificially.In this paper,we design a more general game model as

TABLE I NOTATIONS IN THE PAPER

IV.RELATIONSHIP AMONG COVER STATES AND SNE

In this section,we further study the relationship among the LMWVC,the GMWVC,the NCE and the SNE states.We first give a lemma as follows.

Lemma 1:If all elements in utility matrixMsatisfy the following conditions:

1)b2?d2>max{c2?a2,c1?a1,c?a};

2)b?d>max{c2?a2,c1?a1,c?a};

3)b1?d1

Theorem1:Consider an undirected weighted graphG.If all elements in utility matrixMsatisfy the conditions of Lemma 1,then,we have{VGMWVC}?{VSNE}?{VNCE}?{VLMWVC}?{VWVC}.

NCE,i.e.,{VSNE}?{VNCE}.

Finally,we prove that {VGMWVC}?{VSNE}.Suppose a setS∈{VGMWVC},andS?{VSNE}.Thus,there exists a playervi∈Scan change his strategy to obtain a higher utility.

Since every LMWVC state is a WVC state,we have{VLMWVC}?{VWVC}.

The relationship among the WVC,the LMWVC,the NCE,the SNE and the GMWVC is illustrated in Fig.2.Note that the authors in [35],[36] gave a relationship among the states,i.e.,{VGMWVC}?{VSNE}?{VWVC},where the SNEs in [35],[36] are: for each vertexvi,1) if=D,then it has onlyCneighbors and 2) if=C,then it has at least oneDneighbor.In this case,it is easy to check that the SNEs are equivalent to the LMWVC states in Definition 2.However,the SNE state of the games in [35],[36] only considered whether the neighbor is covered,but ignored the weights of neighbors.That is,the covered strategy is selected if there are uncovered neighbors,and an uncovered strategy is selected if all neighbors are covered.In this paper,the covered strategy is selected only when the weight of the uncovered neighbors is greater than the weight of focused vertices,which results in{VSNE}?{VLMWVC}(the SNEs of [35],[36]).

Fig.2.Relationship among the WVC,the LMWVC,the NCE,the SNE,and the GMWVC states.

V.DISTRIBUTED OPTIMIZATION ALGORITHM

A.Game-Based Asynchronous Algorithm

In this section,we propose a game-based asynchronous algorithm(GAA) for solving the WVC problem.The pseudocode of the GAA is shown in Algorithm1.At each iteration,each player only uses the information (strategy) of the previous iteration,i.e.,the memory lengthmof each player is 1.Moreover,we use strategyto represent the opposite strategy of strategyi.e.,if=C,then we have=D;if=D,then we have=C.

An example is shown in Fig.3 to illustrate why we use an asynchronous game.The graphGin Fig.3(a) is a star graph,where the center playervihas weight 3,other players have a weight of 1,and the initial strategy for each player is strategyC.If all players make decisions simultaneously,then the process may fall into an endless loop.Sinceplayerviwill change his strategy fromCtoD,and other players will also choose strategyD.At the next iteration,all players will change their strategy fromDtoC.Thus,the loop goes on infinitely.The proposed GAA can avoid such a loop.In the GAA,at each iteration,each player updates their strategy sequentially.We take Fig.3(b) as an example,where the center playervimakes a decision first,and changes his strategy fromCtoD,and other players make their decision sequentially.Finally,we obtain a graph,which a covered (C)player surrounded by uncovered (D) players,the state of the network satisfies an SNE.

Fig.3.Update mechanisms.(a) Synchronous update;(b) Asynchronous update.

Lemma 2:Consider an undirected weighted graphG.If all elements in utility matrixMsatisfy the conditions in Lemma 1,then by employing the GAA,any strategy profile satisfies the WVC state after an iteration.

Theorem 2:Consider an undirected weighted graphG.If all elements in utility matrixMsatisfy the conditions in Lemma 1,then,by employing the GAA,the total weight of the covered vertices is decreased by at least αminbefore each player’s state reaches an unchanging state,i.e.,

Fig.4.A simple undirected weighted graph.

Proof:By Theorem 2,the total covered weightafter each iteration is reduced by at least αmin>0.Combining it with Lemma 2,we obtain a WVC state after each iteration,whose total covered weight is smaller than that of the previous iteration.Thus,the number of iterations is not infinite.

Corollary 1:Consider an undirected weighted graphG.If all elements in utility matrixMsatisfy the conditions of Lemma 1,andwv1=···=wvn,then,the GAA can guarantee that any strategy profile converge to an SNEin timeO(n2).

B.Improved Game-Based Asynchronous Algorithm

The proposed GAA in the previous subsection can theoretically guarantee that we obtain an SNE.However,there also exist a shortcoming: The proposed GAA can easily obtain a poor SNE.We will give an example to illustrate it.

Example 3:Fig.5 shows two possible solutions by employing the GAA.Figs.5(a) and 5(b) are both NCE states,where the total covered weightof Fig.5(a) is greater than that of Fig.5(b).Thus,we want to obtain the state of Fig.5(b),but the GAA does not necessarily guarantee this state.

Fig.5.Two possible output solutions of the proposed GAA.(a) The total covered weighted is 40;(b) The total covered weighted is 38.

We can observe that the GAA only uses information in the 1-hop neighborhood,which will limit solution efficiency.Thus,we try to use information about nearby players to improve solution efficiency,and consider anl(l≥2)-hop adjustment mechanism(the region in the closed curve),which satisfies the following two conditions:

1) In the closed region,the total weight of players with strategyDis smaller than that of players with strategyC;

2) In the closed region,for any player with strategyC(D),his neighbors with strategyD(C) are also in this region.

Then,all players in the closed region change their strategy,and can obtain a smaller total covered weight.In Fig.6,we consider a 2-hop adjustment mechanism,then Fig.6(a) will turn into Fig.6(b) .In Fig.7,we consider a 3-hop adjustment mechanism,after which Fig.7(a) will turn into Fig.7 (b).

Based on the above analysis,we further propose a novel algorithm,i.e.,the so-called improved game-based asynchronous algorithm(IGAA).Compared with the GAA,the IGAA not only increases the players’ memory length,but also adds a 2-hop and 3-hop adjustment mechanism.Note that the memory lengthm=1 of the GAA is 1.The pseudo-code of the IGAA is shown in Algorithm2.

When the memory lengthm=1,and the updated strategy is the strategy of the memory space,the random selection in Line 12 will not change the strategy.In this case,Lines 3?13 is the process of the GAA.We give an example to illustrate it.

Fig.6.2-adjustment mechanism.(a) Subgraph before adjustment;(b) Subgraph after adjustment.

Fig.7.3-adjustment mechanism.(a) Subgraph before adjustment;(b) Subgraph after adjustment.

Proof:We first prove that the IGAA with memory lengthm=1will converge to an SNE.By using the IGAA,any strategy profile transitions to a NCE state at the end of Line 13.Suppose a 2-hop adjustment or 3-hop adjustment occurs on a WVC setVWVC.Since the strategyDis changed toC,this will not break feasibility (i.e.,the network still satisfies the WVC state after the change).Thus,we only consider two cases: 1) If playervjchanges the strategy fromCtoDin Line 17,thenvj∈Since each player inchanges their strategy fromDtoC,thus every edge connected to vertexvjhas one covered player;2) If playervjchanges their strategy fromCtoDin Line 20,thenvj∈Similarly,every edge connected to vertexvjhas one covered player.

Next,we prove that the IGAA with memorym=1 will converge to an SNE in finite time,which is no worse than that of the GAA.Only when the covered weight is strictly reduced in Lines 16 and 19,can the strategy be transformed.Thus,at end of Line 23,we obtain a WVC state,whose total covered weight is not higher than that of the GAA.According to Lemma 1,execute Lines 3?13,the total covered weightwill strictly decrease before reaching an SNE.Thus,if a NCE state obtained at the end of Line 13 does not change Lines 14?23,then the IGAA terminates at Line 24.

Consider an undirected weighted graphG,where the number of strategy profiles is at most 2n.Thus the IGAA terminates in finite time.In sum,when memory lengthm=1,the IGAA will converge in finite time to an SNE,which is no worse than that of the GAA.

Fig.8.Comparison among RGMA,GAA,and IGAA on ER,WS,BA,and Grid networks,the memory length m=1.

Note that when the memory lengthm=1,Lines 1–13 of the IGAA is the process of the GAA.When memory lengthm>1,the probability that the latest best response is selected is 1/m.Thus,there is a positive probability for the IGAA converge to an SNE.Further,the IGAA eventually converges to an SNE.

VI.NUMERICAL RESULTS

To evaluate the performance of the proposed algorithm,this section presents numerical simulation results on different weighted networks,including Erd?s-Rényi (ER) random networks [37],Grid networks [38],Watts-Strogatz (WS) smallworld networks [39],and Barabási Albert-László (BA) scalefree networks [40].

We use the greedy algorithm(GA) as a baseline,where the GA starts from an empty set,and at each iteration adds a vertex which has the smallest cost-effectiveness.Here,the costeffectiveness is the cost ofvidivided by the number of edges new ly covered byvi.We regardPG=rY/rGAas a main measure for performance [36],whererYandrGAare the weights of each solution’s output with algorithmsYand GA,respectively.

A.Memory Length m=1

TABLE II THE AVERAGE RUNTIME OF THE RGMA,GAA,AND IGAA (m=1)

TABLE II THE AVERAGE RUNTIME OF THE RGMA,GAA,AND IGAA (m=1)

Fig.9.Comparison among MBR,RGMA,FBR,and IGAA on ER,WS,BA,and Grid networks,the memory length m=2.

B.Memory Length m=2

C.Memory Length m=30

In this subsection,we consider a large memory lengthm,i.e.,m=30,and the related results are shown in Fig.10.As shown in Fig.10,the results of memory lengthm=30 are the same as that of memory lengthm=1 (m=2).The average runtimeof the RGMA,the FBR,the MBR,and the IGAA are recorded in Table IV,in which the average runtimeof the IGAA are much more close and reasonable for all networks.In sum,whenm=1,2 or 30,compared with typical algorithms,the IGAA can obtain the best results in terms of thein a promising computation time.

The algorithms RGMA,FBR,MBR can ensure any strategy profile converge to SNE in [35],[36] and the GAA,IGAA can ensure any strategy profile converge to an SNE defined in this paper.Moreover,the solution state for the IGAA is more closer to the GMWVC state than the solution state for the MBR,the FBR,the RGMA and the GAA.

VII.CONCLUSIONS

In this paper,we have defined several new cover states,i.e.,the GMWVC state,the LMWVC state,and the NCE state.Moreover,we have designed a general game model framework to describe the WVC problem of weighted networks,and proven that the LMWVC states are the intermediate states between the NCE and the WVC states,and further proven that the SNE of the designed game model is the basis of the connection between the GMWVC and the NCE states.Then,we proposed a GAA,which ensures that any strategy profile converges SNE in the polynomial time.Furthermore,we have improved the GAA (called IGAA),which is superior to the GAA in terms of solution efficiency.The numerical simulations have shown that the proposed IGAA can obtain a better approximate solution in promising computation time,which is competitive with the other existing typical algorithms.

TABLE III THE AVERAGE RUNTIME Tˉ OF THE RGMA,FBR,MBR AND IGAA (m=2)

Fig.10.Comparison among MBR,RGMA,FBR,and IGAA on ER,WS,BA,and Grid networks,the memory length m=30.

TABLE IV THE AVERAGE RUNTIME Tˉ REQUIRED FOR THE RGMA,FBR,MBR,AND IGAA (m=30)