- Free Articles
- Suffix Tree Construction in Hierarchical Memory Encyclopedia of Algorithms
- Probabilistic Data Forwarding in Wireless Sensor Networks Encyclopedia of Algorithms
- Renaming Encyclopedia of Algorithms
- Time in Philosophical Logic Encyclopedia of Database Systems
- Indoor Localization Encyclopedia of GIS
**More Free Articles**

This is the free portion of the full article.
The full article
is available to licensed users only.

How do I get access?

# Vertex Cover Kernelization

## Keywords and Synonyms

## Problem Definition

Let *G* be an undirected graph. A subset *C* of vertices in *G* is a *vertex cover* for *G* if every edge in *G* has at least one end in *C*. The (parametrized) vertex cover problem is for each given instance (*G*, *k*), where *G* is a graph and *k*≥0 is an integer (the parameter), to determine whether the graph *G* has a vertex cover of at most *k* vertices.

The vertex cover problem is one of the six "basic" NP-complete problems according to Garey and Johnson [4]. Therefore, the problem cannot be solved in polynomial time unless P = NP. However, the NP-completeness of the problem does not obviate the need for solving it because of its fundamental importance and wide applications. One approach was initiated based on the observation that in many applications, the parameter *k* is small. Therefore, by taking the advantages of this fact, one may be able to solve this NP-complete problem