Vertex Cover Optimization Using a Novel Graph Decomposition Approach

Abdul Manan,Shahida Bashir and Abdul Majid

1Department of Mathematics,University of Gujrat,Gujrat,50700,Pakistan

2Department of Physics,University of Gujrat,Gujrat,50700,Pakistan

Abstract:The minimum vertex cover problem (MVCP) is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial) complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.

Keywords:Combinatorial optimization;graph theory;minimum vertex cover problem;maximum independent set;maximum degree greedy approach;approximation algorithms;benchmark instances

1 Introduction

The Minimum Vertex Cover Problem (MVCP) is a subset of NP complete problems.Solution of NP class of problems is one of the seven outstanding millennium problems stated by the Clay Mathematics institute.The solution of these problems can be verified in polynomial time scale,but time complexity for solving these problems grow exponentially with size of the problems[1].The MVCPinvolves finding a setUsuch thatU⊂V.Here the setUhas the smallest possible cardinality in a graphG=G(V,E)such thatVis a set of vertices andEis a set of edges of the graph.For the setUto be a cover of graph,every edge of the graph is connected to at least one element ofU.The setUis called a minimum vertex cover ofG[2].The problem has an exponentially growing complexity since the number of combinations which are required to be verified grows asnv!wherenvrepresents the number of vertices in the graph.Due to exponential growth in complexity of the problem,it is almost impossible to exactly solve the problem in a realistic time scale.Therefore,solving these problems via Brute force method i.e.,checking all the possible combinations is not feasible.However,one may opt for an approximate solution of these problems in a reasonably quick time.

The MVCP has a wide range of applications;for example,cyber security,setting up or dismantling of a network,circuit design,biochemistry,bioinformatics,electrical engineering,data aggregation,immunization strategies in network,network security,internet traffic monitoring,wireless network design,network source location problem,marketing and franchising,pattern recognition and cellular phone networking[3-9].

Due to its wide range of applications,the MVCP has received special attention in the scientific community.Several approximate algorithms for solving the problem have been proposed,e.g.,the depth first search algorithm,the maximum degree greedy algorithm,the edge weighting algorithm,the deterministic distributed algorithm,the genetic algorithm,the edge deletion algorithm,the support ratio algorithm,the list left algorithm,the list right algorithm and iterated local search algorithm etc[10].Since all these algorithms provide approximate results with certain accuracy,there is a certain space to improve accuracy and to reduce complexity by introducing faster and more accurate algorithms.The scientific community around the globe has proposed approximate solutions of the problem with polynomial complexity.Some of the efforts by scientific community are described in following paragraph.

Jiaki Gu et al.proposed an algorithm that uses a general three stage strategy to solve the minimum vertex cover problem.Their method includes graph reduction,finding minimum vertex cover of bipartite graph components and finally finding the vertex cover of actual graph[11].Changsheng Quan and coworkers proposed an edge waiting algorithm to solve MVCP.They claim that their algorithm has a fast-searching performance for solving large-scale real-world problem[12].Shaowei Cai et al.in their work proposed a heuristic algorithm that make use of a preprocessing algorithm,construction algorithms and search algorithms to solve the MVCP.They claim that their algorithm is fast and accurate as compared to other existing heuristic algorithms[13].Chuan Luo et al.proposed an algorithm that uses a highly parametric framework and incorporates many effective local search techniques to solve the MVCP.According to their claim their algorithm performs better for medium size graph and is competitive for large sized graphs[14].

Jinkun Chen and coworkers proposed an approximate algorithm based on rough sets.They use a Boolean function with conjunction and disjunction logics[15].Cai.S et al.in their work use an edge weighting local search technique for finding an approximate MVC[16].Khan,I and coworkers proposed an algorithm that works by removal of nodes to find a maximum independent set yielding an approximate MVC[17].Arstrand,M et al.formulated a deterministic distributed algorithm to solve the MVCP.The authors solved the problem for two approximate solutions of the MVC during(Δ+ 1)2synchronous communication rounds whereΔrepresents an upper bound of maximum degree[18].Bar-Yehuda et al.used Dijkstra algorithm in their work in order to solve the problem[19].Genetic algorithm has been used for the solution of the problem by Bhasin et al.Their algorithm demonstrated advantage of handling graphs when compared to the reported literature algorithms.The authors mentioned that the algorithm is unable to tackle some problems due to which they proposed the usage of Diploid Genetic Algorithms as an extension[20].Support Ratio Algorithm(SRA)used a heuristic approach to solve the MVCP in which Balaji and coworkers used an adjacency binary matrix to represent a graph.The complexity of the algorithm has beenwherenis numbereof edges andnvis the number of vertices.The authors claim that the support ratio algorithm has been found better for large scale problems compared to the reported algorithms[21].Kettani and co-workers introduced a novel heuristic algorithm to find MVC.The author suggested to use their algorithm for other graph optimization problems including maximum clique problem[22].Xu and Kumar proposed a solver for the minimum weighted vertex cover problem(MWVC).Their algorithm reformulated a series of SAT(satisfiability)instances using a primal-dual approximation algorithm as a starting point[23].Ruizhi Li,and coworkers proposed a local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem[24].For hypergraphs and bounded degree graphs Halperin and co-workers proposed an algorithm to find minimum vertex.They used semi-definite programing and introduced a new rounding technique for this purpose[25].Cai,S.et al.have reported an algorithm based on local search(NuMVC)that has been found efficient in finding MVC.They introduced two new processes that involve a two-way exchange and an edge weighting mechanism[26].

The literature survey indicates variety of results as far as complexity and accuracy of algorithms are concerned.Onak and Rubinfeld developed a randomized algorithm for maintaining an approximate maximum cardinality matching with a time complexity ofO(log2nv)[27].

In particular,the present work is more suitable for two dimensional graphs with triangular grid structures.The two-dimensional triangular grid graphs are very common in telecommunications,in molecular biology,in configurational statistics of polymers and in various other fields[28-30].We are proposing here a new way to find edges shared by such triangular grid structures and use these subgraphs to simplify the MVC for such graphs.

2 Definitions

A graph can be represented as a matrixMe(Edge Matrix or Adjacency Matrix)such that;

Hereiandjare numbered vertices such thati,j∈V.

The setN(k)is the set of neighbors of thekthvertex in the graph.The set of edges connected by thekthvertex is represented bykthrow orkthcolumn of the edge matrix.The removal of thekthrow andkthcolumn from the edge matrixMeis equivalent to the removal of thekthvertex and all of its incident edges from the graph.

From here onward letHOdenote a Hamiltonian cycle with odd number of edges (subgraphs of the form triangles,pentagons and heptagons etc.),HTdenote a Hamiltonian cycle with three edges(triangles only),a common or shared edge here is defined as an edge that is shared by more than one Hamiltonian cycles of the formHO.A Hamiltonian cycle with three edges i.e.,HTcan be represented aseijejkeki= 1,wherei,jandkare the three vertices of that Hamiltonian cycle.Similarly,for any odd number of verticesi,j,k,l...zone can represent the Hamiltonian cycleHOaseijejkekl...ezi= 1.

Any vertexw∈Vcis said to be covered,Vcdenotes here the vertex cover of a graph.ABimplies all those elements of a setAwhich are not elements of set B and a shared vertex is defined here as a vertex that has a degree greater than two.

3 Proposed Work

A graph can be divided into a number of subgraphs such that;

A solution for graph decomposition is proposed that is based on Lemma and Theorem proved below.

Lemma:An edge that has both of its vertices covered must belong to a Hamiltonian cycle or a path with odd number of edges.

Proof:A graph can be decomposed into a number of subgraphs that may be a Hamiltonian cycle or a path with odd or even number of edges.For even number of edges a Hamiltonian cycle or path does not require both vertices of any edge to be covered.For a Hamiltonian cycle with odd number of sides only one of the edges must have both vertices covered.For paths with odd number of sides both vertices of one of those edge may or may not require to be covered.Hence,if both vertices of an edge are covered that edge may either be an edge of a Hamiltonian cycle or a path with odd number of edges.

Theorem:The exact minimum vertex cover of a graphGcan be found by constructing a subgraph from edges(x,y)∈HOand finding minimum vertex cover of the subgraph,wherex,y,(x,y)∈G

Proof:For a given set of vertex cover there may exist at most two types of edges depending on the vertices being covered i.e.,an edge with both of its vertices covered and an edge with a single vertex covered.The edge with both vertices covered essentially belongs to a subgraph of the form of a path or a Hamiltonian cycle with odd number of edges as proved in the Lemma.In case of two different set of vertex covers i.e.,an optimum vertex cover and an approximate one,there can be at most five cases,which are listed below;

Case 1:An edge(x1,y1)covered by both verticesx1andy1in the set of optimum vertex cover and covered by a single vertex(eitherx1ory1)in approximate set of vertex cover.

Case 2:An edge(x2,y2)covered by a single vertex(eitherx2ory2)in the optimum set and covered by both vertices(x2andy2)in the approximate set.

Case 3:An edge(x3,y3)covered by both verticesx3andy3in both sets.

Case 4:An edge(x4,y4)covered by a single but different vertex in both sets.

Case 5:An edge(x5,y5)covered by a single and same vertex in both sets.

For both of the sets the number of cases like case 3,4 and 5 are the same i.e.,such cases do not cause any difference on the cardinality of both sets.In cases 1,2 and 3 at least one of the sets have its edges covered by both vertices.Since case 3 is the same for both the sets,the only two cases that can cause difference on the cardinality of both sets are case 1 and 2.For the approximate set the number of cases like case 2 is greater than or equal to the number of cases like case 1.This leads to the fact that a large number of cases like case 2 can increase cardinality of an approximate set compared to the optimal set.All edges that belong to subgraphs that are either paths or Hamiltonian cycles with odd number of edges are candidates of having both vertices in the vertex cover.By simply separating all such edges the optimization problem simplifies.

This leads to a conclusion that minimum vertex cover optimization depends only on optimization of subgraphs formed by Hamiltonian cycles or paths with odd number of sides.

Based on the Theorem a new approach is proposed to findu∈U,approximately,andCiexactly,and hence an approximate minimum vertex cover of the formIn principle,any subgraph of the formHOmust have both vertices of one of its edges in the vertex cover.This work is based on finding edges that satisfieseij∈HT.Removal of these edges from the graph assuresEi∩Ej= Ø which is followed by removal of common or shared vertices to result in disjoint graphs satisfyingGi∩Gj= Ø.

Our aim here is to find edges,which are common in more than one triangular Hamiltonian cycle.We refer such edges as shared edges.To find such shared edges in a large graph we are proposing a new approach.The new approach is based on decomposition of a graphG(V,E)into two subgraphsGUandGSin such a way that an edgeeij∈GSsatisfieseij∈HOfor at least two subgraphs of the formHO(referred here as shared edges)inG,whereas all edges other than shared edges formsGU.A greedy approach can then be used for selecting a vertex fromGS.The selected vertex is then covered.After covering such vertices some of the edges(emn)may no longer satisfy the conditionemn∈HOand hence are moved fromGStoGU,the removal of vertices from ofGSwill eventually result inGS= Ø.At this stage the uncovered graphGUwill contain shared vertices,isolated polygons and/or isolated paths.This subgraph can further be divided into two subgraphsGIandGSV,whereGSVconsists of all the shared vertices and their adjacent edges,andGIconsists of one or more than one isolated Hamiltonian cycles or paths.Both the subgraphsGSVandGIare covered using maximum degree greedy approach.The greedy approach exactly covers the subgraphGIThis work is limited to find subgraph of the form ofHT.i.e.,the set of all shared edges of all triangles in a graph.This can be done by finding common neighbors of all edges of the graph.For verticesiandkthat form edgeeik,the common neighbors can simply be found by an intersection of a subgraphN(i)with subgraphN(k).The setN(i)∩N(k),is found by carrying out AND operation ofithrow or column withkthrow or column of the edge matrixMe.One can write;N(i)∩N(k)=eij∧ejk,wherej= 1,2,3,...,nvandnvis the total number of vertices in the graph.The intersection yields the common neighbors ofithandkthvertices.One can evaluate square of the edge matrix as;

For example,tik≥2 corresponds to a subgraph which forms two or more than two triangles with a shared edgeeik.For all the cases withtik≥2,the verticesiandkare the minimum vertex cover of the subgraph.Fortik= 0,implies either the edge is not shared oreik /∈G.Fortik= 1,the subgraph forms a single triangle.The valuetik=0,implies thateik /∈HT,buteik∈HOmay still be possible.A subgraphGSof all edges satisfyingeik∈HTcan be generated using the weight matrixTefortik≥2.However,if all the edges of a graph are shared edges,the conditiontik≥2 will produce a graph of shared edges same as the original graph i.e.,GS=G.For such graphs one can modify the condition astik≥tmin+n,wheretminis minimum number of triangles sharing a single edge in that graph andnis a small number.This modification will generate a reduced graph of shared edges.A vertex cover of the reduced subgraphGSremoves all shared edges of the formeik∈HTfromG.However,the conditioneik∈HOmay still not be satisfied.

Removal of any subset of vertices from a graph requires removal of the corresponding row or column from the edge matrixMe.This leads to calculation of new square matrixSe.However,instead of calculatingSefrom scratch,a low-cost solution is proposed here to reduce the simulation time.

Algorithms

The decomposition of a graphGintoGUandGS(The subgraph containing all shared edges of triangular structures) is accomplished by transforming the matrixTe→Wesuch that[We]ij=min（1,[Te]ij）andtik≥2.The algorithm is divided into three stages.In first stage a vertex with highest degree in the subgraphGSis found and covered.The first stage is terminated whenGS= Ø.The subgraphGUdoes not contain any shared edge that belongs to triangular structures but it may still have edges shared by subgraphs of the formHO.In second stage,the vertex with highest degree is found fromGUand covered.After covering all the shared vertices of the graph,the graph is left with isolated paths or polygons.In third stage,a vertex with degree 2 is found and covered.The removal of a vertex fromGin all three stages may lead to leaves in the residual graph.Therefore,these leaves are removed by covering their adjacent vertex.

The proposed algorithms are described in the following section.Algorithm 1 and Algorithm 2 are abbreviated as ASE and ASER such that‘A’stands for Algorithm,‘SE’stands for‘Shared Edges’and‘R’stands for‘Reduction Strategy’.

Algorithm 1:(ASE)· Input:Graph G(V,E).· Output:Minimum Vertex Cover of graph G(V,E).1:Read data and construct edge matrix Me and We 2:while size(Me)＞1

Algorithm 1:Continued 3:while(size(We)＞1)4:Perform operation(A0),(A1),(A2),(A3)and(A4)5:end 6:while (deg(v ∈V)≥2)7:Perform operation(A5),(A6),(A3)and(A4)8:end 9:end

(A0)EvaluateWeusing matricesMe,SeandTefortik≥2 ortik≥tmin+3

(A1)Find a vertex with highest degree fromWeand cover the vertex

(A2)Evaluate matrixFfor the vertex found in step A1.Using Eq.(4)evaluate reduced matrixSeusing matrixFand the matricesMeandSefrom step A1.Reduce matrixMe.

(A3)Remove all leaves from the graph

(A4)Remove all isolated vertices from the graph

(A5)Find deg(u∈U),i.e.,degree of vertexuin present set of verticesU

(A6)Find the vertexuthat has the maximum degree in present graph,cover the selected vertexuand remove from the graph.

Complexity

Total complexity of the algorithm is（34nv3-99nv2+170nv-120）/241.42nv3.

To reduce complexity of ASE a reduction strategy is proposed.The reduction strategy consists of splitting graph into two subgraphs and finding independent set of 1stsubgraph and taking union of that independent set with 2ndsubgraph and finding independent set of the union set.However,this graph splitting is not random.For splitting one can list the set of edgesE={(λ,μ):μ∈N(λ),∀λ,μ∈E}.Construct two sets of verticesL={λ:∀(λ,μ)∈E}andR={μ:∀(λ,μ)∈E}.FindL∩R.One can see that the set,IL=LL∩Ris an independent set,because there are no two vertices inIL,that are neighbors of each other.Similarly,IR=RL∩Ris also an independent set.

Under normal circumstances the list of edgesEmay not provide reasonably largeILandIR,therefore,one may need to prepare the list the edgesEso thatILandIRare sufficiently large.One may opt for an alternative strategy to find sufficiently largeIL,IRand a smallVres=L∩Rby using a lowcost algorithm that can find an approximate minimum vertex cover.The low-cost algorithm outputs an independent set and residual set of vertices.Therefore,one can use the low-cost algorithm twice to findILand(VIL)and again to findIRand(VIL)IRand remaining set of verticesVres=L∩R.Now one can construct a subgraph fromVres,that isGres=Gres(Vres,Eres).An independent setIrescan be found using Algorithm 1(ASE).A second subgraph can be constructed fromIs=IL∪IR∪Ires,that isGS=GS(IS,ES).Using Algorithm ASE again one can construct the final independent set.Complexity of this algorithm depends on the cardinalitynLofILandnRofIR.The cardinality of set of vertices of the 1stsubgraph isn1=nv-nL-nRand cardinality of set of vertices of 2ndsubgraph isn2=nres+nL+nR,wherenresis the cardinality of the setIres.The complexity of algorithm ASER is.

(B0)Find an independent setIsof a graph using a low-cost algorithm

(B1)Construct residual subgraphGR(VR,ER)fromVR=V-Is.

(B2)Construct a single set using three sets as;Is=Is1∪Is2∪Is3

(B3)Find maximum independent set of given subgraphs using algorithm 1

(B4)Find a subsetIcof the vertex coverVc,such thatIccontains vertices that individually can go to independent setIind.Find independent set ofIcusing Algorithm1.Move all vertices of that independent set toIindto construct the final independent set.

The low-cost algorithm simply selects and adds a vertex to an independent set followed by searching vertices that can be moved to the independent set.This algorithm has a complexity ofnv2/2.However,one is free to choose the low-cost algorithm in accordance with the suitability.

4 Results and Discussion

In this section both the algorithms are tested and analyzed for their accuracy and complexity for benchmark graphs taken from[31,32]and[33].The simulations are performed on a computer with 1.61 GHz processor and 8.00 GB RAM using sequential programming.

The results from the 72 benchmark graphs referred above are organized in the form of three tables.Tabs.1 and 2 contain optimum vertex cover and accuracy in the form of error ratios for the algorithms of respective graphs.Tab.3 contains a comparison of results of the algorithm ASE with three well know algorithms.The error ratio is defined here as the value of minimum vertex cover for a given graph obtained from each algorithm divided by the optimum vertex cover(nO)of that graph.The conditiontik≥2 has been used to generate shared edges graph(GS)for 64 benchmark graphs.For some of the benchmark graph all the edges are shared edges,therefore,the conditiontik≥2 will yieldGS=G.For such graphs the condition is modified totik≥tmin+ 3,wheretminis minimum number of triangles sharing a single edge in that graph.This modification results in reduced shared edges graph.The conditiontik≥tmin+3 is used to generateGSfor eight such graphs and their error ratios are given in Tab.2.

Table 1:The calculated MVC and error ratio for the proposed algorithms for tik ≥2(c stands for clq and cc for clq_compliment)

Table 1:Continued

Table 2:The calculated MVC and error ratio for the proposed algorithms for tik ≥tmin+3

Table 3:Comparison of ASE with MDG,MVSA and MtM

Table 3:Continued

Fig.1 shows the error ratio(ϵr)obtained from both the algorithms plotted against the number of vertices for 67 benchmark graphs(excluding the graph with number of vertices greater than 2000 for better visibility of the figure).The solid line in Fig.1 corresponds to the error ratio for optimum vertex cover.It can be seen that the error ratio for graphs with fewer number of vertices is less accurate compared with that of the higher number of vertices.This suggests that the algorithms get better and better with increased number of vertices.It can also be noted that the worst-case error ratio(ϵr)for algorithms ASE and ASER are 1.025 and 1.038 respectively.An interesting finding of this study is the reported optimum error ratio for few benchmark graphs in literature is found slightly less accurate compared to the value calculated in this work.This can be seen in Fig.1 as ASE and ASER lies below the optimum error ratio line on six and three occasions,respectively.

Figure 1:Accuracy of the suggested algorithms,solid line represents reported optimum values

As can be seen from the Tabs.1 and 2 that out of 72 instances ASE and ASER both give an error ratio(ϵr=1)or better on 55 and 50 instances,respectively.The average error ratios(ϵr)for ASE and ASER are 1.0017 and 1.0030 respectively.

In ASE,since only edgesemn∈HTare covered,all edges satisfyingemn∈HOare not covered with certainty.This may lead to erroneous results.After covering all edges from subgraphs of the formHT,shared vertices are selected with the priority of highest degree of the residual graph,and the vertices are moved to vertex cover one by one.The selection may not be accurate since it uses the greedy approach.However,the approach will produce exact minimum vertex cover for the residual graph that is left with isolated Hamiltonian cycles or paths.

Supplementary data describes the complexity of the proposed algorithms and contains two parametric numbers or reduction parameters p1and p2.Supplementary data also contains time taken by each of the algorithm to find the minimum vertex cover.The reduction parameter is the ratio of approximate complexity of the form（of an algorithm with that ofand can be is calculated aswhere n1and n2are defined in the previous section.These reduction parameters represent a time reduction of an algorithm with reduction strategy(ASER)to the same without reduction strategy(ASE).

The comparison between ASE and ASER is given in Fig.2,which shows that if either p1→1 or p2→1,a difference between their simulation times approaches to zero.For graphs hamming6_2_clq_compliment,hamming8_2_clq_compliment and hamming10_2_clq_compliment,one can see that p1→1 and p2→0,hence no significant time difference is observed.Similarly,for graphs p_hat700_1,MANN_a27,MANN_a45 and C2000_9 reduction parameters p1→0 and p2→1,forcing the time difference to approach to zero.A noticeable difference in simulation time can be observed for the cases where neither p1→1 nor p2→1.The reduction parameters p1and p2for each of the benchmark graphs are plotted in Fig.2.

Figure 2:Reduction parameters p1 and p2 plotted against number of vertices

The simulation time for the proposed algorithms is plotted against the number of vertices in Fig.3.A cubic fit function of the formis also plotted to show the complexity trend of both the algorithms.It can be seen that the algorithms(ASE and ASER)follow the cubic fit trend.Since computer takes a small amount of preprocessing time before each simulation,one can see that for low values of nvthe simulation time is large compared to f(nv),whereas for large values of nvthe simulation time matches with f(nv).One can also see that simulation time for ASER is occasionally smaller than f(nv),reflecting a success in reduction strategy.

Figure 3:Simulation time vs.the number of vertices for the proposed algorithms

In Tabs.1 and 2 the performance of the algorithm ASE is evaluated using 72 benchmark graphs.On 48 instances our algorithms yield optimal values.In Tab.3 we have compared the results for 20 benchmark graphs for which ASE does not yield optimal values with three well known algorithms MDG (maximum degree greedy)[34],MVSA (modified vertex support algorithm)[35]and MtM(Min-to-Min)[36].The average ratio error for these 20 benchmark graphs presented in the Tab.3 for ASE,MDG,MVSA and MtM are,1.005,1.014,1.015 and 1.012,respectively.This shows that the algorithm ASE clearly outperforms the three algorithms in comparison.

5 Practical Implementation

For step-by-step analysis of the algorithm a simple real-life example is selected.Crypto or digital currency market currently has a market capital of billions of US dollars.There are hundreds of crypto currencies with billions of USD daily volume.Market data analysis of these currencies is becoming harder and harder with growth in data.However,almost all of these currencies are paired with each other for trading.Therefore,any market fluctuation is coupled within these crypto currencies.In principle,one can represent these currencies and their trading pairs in the form of a graph and can find minimum vertex cover of the graph to select only few currencies for crypto market data analysis.We have selected ten crypto currencies and their trading pairs in order to simplify the problem.These crypto currencies and their trading pair are presented in the form of a graph is shown in Fig.4a.

The graph is decomposed in subgraphs with bold dark lines showing shared edges and dashed lines as the rest of the graph.The shared edge graph is simply a triangle in this case and each vertex has a degree 2 in the subgraph.A single vertex (in this case vertex 1) is covered,i.e.,Vc= {1} and we are left with only a single edge(e23)in the subgraph.One vertex(vertex 2)of the remaining edge(e23)is covered,yieldingVc= {1,2}.Since there are no more shared edges in the graph,therefore we are left with the subgraph of the form shown in Fig.4b.From here on ward the vertices are simply covered on the basis of their degree.Since the vertex 3 has the highest degree therefore,it is covered,yieldingVc={1,2,3}and hence the entire graph is covered.A conclusion of this process is that,only crypto currencies numbered 1,2 and 3 represent the complete variation of the market for only these ten crypto currencies.However,in order to completely analyses the entire crypto market a minimum vertex cover of a graph representing entire market has to be found.

Figure 4:(a)Crypto currencies and their trading pair(b)Subgraph with no shared edge

6 Summary

The proposed approach simplifies a graph to isolated paths or polygons (Hamiltonian cycles)by moving shared edges followed by shared vertices to the vertex cover.This process forms three subgraphs i.e.,a subgraph containing shared edges,a subgraph with shared vertices and finally a simplified subgraph.The final simplified subgraph is either a single Hamilton cycle or path or a number of isolated Hamiltonian cycles or paths.The vertex cover of the simplified subgraph can be exactly found in a short time using maximum degree greedy approach.The accuracy of finding the first two subgraphs depends on the sequence of covering the vertices.The proposed strategies are capable to search for the sequence of selection of vertices to an approximate extent only.However,using this approach the problem can be broken successfully into three smaller problems,which are relatively easy to handle.The worst-case error ratio(ϵr)for algorithms ASE and ASER are 1.025 and 1.038,respectively.The average error ratios(ϵr)for ASE and ASER are 1.0017 and 1.0030 respectively.The algorithms have a maximum complexity of approximately 1.42nv3.Both the algorithms (ASE and ASER) improve optimum error ratio for few graphs compared to the values reported in literature[17,34-36].

7 Future Work

The proposed approach may work even better if all the edges shared by subgraphs of the formHOcan be found and removed with certainty(i.e.,in correct sequence)and if one may find a better strategy(or sequence)to remove shared vertices other than the greedy approach.A future work is suggested to find shared edges among all subgraphs of the formHO.

Funding Statement:The authors received no specific funding for this study.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.