The Vertex Cover Problem - CodeProject

The Vertex Cover Problem - CodeProject

This project discusses different techniques and algorithms used to solve the parameterized Vertex Cover problem. A vertex cover of a graph G(V,E) is a subset of vertices V such that for every edge (u, v) ⊆ E, at least one of the vertices u or v is in the vertex cover. The best algorithm for this problem is known to run at O(1.2852k + kn). The optimal solution is intractable, thus optimization strategies in solving the vertex cover problem are brought off-the-shelves, including pre-processing, kernelization, and branching methodologies. A performance bound is considered for approximation algorithms listed in this research.

Background

Vertex cover problem is a Fixed Parameter Tractable (FPT) problem, where an input k, usually an integer in our case, can be used to minimize the computational density of a problem x. For example, if we have a table with n records and a query of size k, then finding objects in the table that suit the query k can be done in time O(n k). When parameter k is small, this solution can be feasible. Sometimes, it is possible to write a O(n 2 k) algorithm for special tasks; this will also be feasible when the parameter is small. Moreover, a problem with a parameter k is called Fixed Parameter Tractable (FPT) if it can be solved or decided by an algorithm within a running time O(f(k).poly(n)), for some function f. That was the basic approach of Robert Downey and Michael Fellows; they took into consideration the Vertex Cover problem as follows:

Read full article from The Vertex Cover Problem - CodeProject