Exact Algorithms For Minimum Vertex Cover Problem

Vertex Cover is a subset of vertices in an undirected graph G=(V,E),and at least one point on each edge belongs to it.Minimum Vertex Cover(MVC)problem is to find a vertex cover with the smallest number of vertices.The MVC problem is a classical combinatorial optimization problem,which is closely to other difficult problems such as Maximum Clique problem,Maximum Independent Set problem,Minimum Dominating Set problem.In addition,the MVC problem plays an important role in many practical applications such as bioinformatics,computer vision,network traffic monitoring,wireless communication,circuit design,coding theory and so on.Therefore,it has important theoretical significance and application value to research.At present,there are two kinds of algorithms to solve the Minimum Vertex Cover problem: approximation algorithms and exact algorithms.The approximate algorithms can usually give a high-quality solution in a short time,but it cannot prove the optimality of the solution.Exact algorithms don't have this design flaw.The exact algorithms ensure the optimal of solution.In this paper,we propose a branch-and-bound algorithm to solve the Minimum Vertex Cover problem exactly.Since a tight lower bound for MVC has a significant influence on the efficiency of a branch-and-bound algorithm,we define two novel lower bounds to help prune the search space.One is based on the degree of vertices,and the other is based on MaxSAT reasoning.The experiment confirms that our algorithm is faster than previous exact algorithms and can find better results than heuristic algorithms.The algorithm EMVC designed in this paper has excellent performance in DIMACS instance.Nowadays,graphs in the real world usually have very large scales.There usually have millions vertices in the graphs.Another work of this paper is to solve the Minimum Weight Vertex Cover(MWVC)in large sparse graphs.The Minimum Weighted Vertex Cover problem is to find a vertex cover with minimum total weight w in the graph.This paper proposes a novel branch-and-bound(BnB)algorithm to exactly solve the MWVC problem in large graphs.The original contribution is several new graph reduction rules,allowing to reduce a graph G and the time needed to find a minimum weight vertex cover in G.Experiments on large graphs from real-world applications show that the reduction rules are effective and the resulting BMWVC algorithm outperforms relevant exact and heuristic MWVC algorithms.