[attachment=14564]
Abstract:
Given an undirected, unweighted graph G = (V, E), the minimum vertex cover problem is a subset of whose cardinality is minimum subject to the premise that the selected vertices cover all edges in the graph. There are various other algorithms that follows heuristic based approaches, but using those approaches we are not able to find optimal solution always in the same manner Greedy algorithms solves the same problems but some problems have no efficient result, but up to a certain extend the Greedy algorithm may provide a solution that is near to optimal. In this paper we propose an Advance vertex cover algorithm to find optimal solution to the minimum vertex cover problem.
The proposed algorithm produce optimal solution with O(n²) time complexity, Optimality and time complexity is the main subject of this paper.
Introduction
Approximation algorithm
Many problems of practical significance are NP-complete but are too important to abandon merely because obtaining an optimal solution is intractable. If a problem is NP-complete, we are unlikely to find a polynomial-time algorithm for solving it exactly, but even so, there may be a hope. There are at least three approaches to getting around NP-completeness. First, if the actual inputs are small, an algorithm with exponential running time may be perfectly satisfactory. Second, we may be able to isolate important special cases that are solvable in polynomial time. Third, it may still be possible to find near-optimal solutions in polynomial time (either in the worst case or on average). In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an approximation algorithm
Approximation algorithms are used to find approximate (near to optimal) solutions to optimization problems. Approximation algorithms are efficient algorithms that compute approximate (near to optimal) solutions. Approximation algorithms are used for those problems where exact polynomial-time algorithms are known but exact polynomial time algorithms are too expensive due to the increasing input size of problem.
Vertex cover
Vertex cover of a graph
In computer science, the Vertex Cover Problem is an NP-complete problem in complexity theory. A vertex cover in a graph is a subset of the vertices of the graph, chosen with the property that one of the endpoints of each edge is in the subset. Finding the minimum vertex cover (subset of vertices) is a classical optimization problem. The minimum vertex cover problem is the example of NP-hard optimization problem.
.Definition: “A vertex-cover of an undirected graph G= (V, E) is a subset of V`subset of V such that if edge (u, v) is an edge of G then either u in V or v in V` (or both).”
Minimum Vertex Cover Problem
Minimum vertex cover problem is to find the smallest possible set of vertices that covers all the edges in the given graph G.
Definition: - “Given a graph G= (V,E), where V = { vertices in G }and E = {edges in G}.
The minimum vertex cover problem is to find a smallest subset of vertices V’( € V), such that every edge has at least one endpoint in this subset .”
Survey of Literature
As we have seen, many combinatorial optimization problems are NP-hard and thus there is minimum possibilities that we will develop efficient algorithms for these problems. Nevertheless, many of these problems are fundamental and solving them is of great importance.The minimum vertex cover comes under classical optimization problem in computer science. This problem is the example of NP-hard optimization. For this problem we have approximation algorithm. According to the Karp “Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory”
[1]In practice, the minimum vertex cover problem can be used to model many real world situations in the areas of circuit design, telecommunications, and network flow and so on [1]. For example,[2] whenever one wants to monitor the operation of a large network by monitoring as few nodes as possible, the importance of the MVC problem comes into the rule[2].
Because of the computational intractability of the problem, many researches propose approximation algorithms for good solution of minimum vertex cover problem in a reasonable time. [2] An intuitive greedy approach for solving the problem is to successively select the vertex with the largest degree until all of the edges are covered by the vertices in V'. This straightforward heuristic is not a good one as demonstrated by [2].
Many researches present heuristic based solution for minimum vertex cover problem. Any approach that solves the problem without a formal guarantee on the quality of the solution can be considered as a heuristics for the problem. Mostly Heuristic approaches not give optimal solution of the problem but some heuristics provide very good solution in practice.
Following are the papers that have heuristic approach to solve minimum vertex cover problem. Ira pramanick and jon G. Kuhl has proposed “A practical method for computing vertex covers for large graph”. This paper is based on a general heuristic problem solving framework known as Parallel Dynamic Interaction or PDI[4]. In 1982m H. Papadimitriou and K. Steiglitz’s research which is most popular now a days that us based on ant colony algorithm" “A pruning based ant colony algorithm for minimum vertex cover problem “. This paper fellow a meta-heuristic approach based on Ant Colony Optimization (ACO) approach to find approximation solution to the minimum vertex cover problem [1]. Another approximation based approach is given by Pietro S. Oliveto, Jun He, and Xin Yao in their research paper “Analysis of the (1+1)-EA for finding approximation solution to vertex cover problems”. Evolutionary algorithms (EAs) are randomized search heuristics that have been widely used for solving combinatorial optimization problems since the 1970s [5].
In the field of minimum vertex cover problem there are various other algorithms that follows heuristic based approaches, but not included in this paper.
Most of the researchers follow the greedy approach but the greedy approach not produces optimal solution. Greedy algorithms solve problems by making the choice that seems best at the particular moment. Many optimization (i.e. vertex cover problem) problems can be solved using a greedy algorithm. Some problems have no efficient solution, but a greedy algorithm may provide a solution that is close to optimal.