Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Vertex cover
Summary
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations. It is a typical example of an NP-hard optimization problem that has an approximation algorithm. 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. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.
The minimum vertex cover problem can be formulated as a half-integral, linear program whose dual linear program is the maximum matching problem.
Vertex cover problems have been generalized to hypergraphs, see Vertex cover in hypergraphs.
Formally, a vertex cover of an undirected graph is a subset of such that , that is to say it is a set of vertices where every edge has at least one endpoint in the vertex cover . Such a set is said to cover the edges of . The upper figure shows two examples of vertex covers, with some vertex cover marked in red.
A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number is the size of a minimum vertex cover, i.e. . The lower figure shows examples of minimum vertex covers in the previous graphs.
The set of all vertices is a vertex cover.
The endpoints of any maximal matching form a vertex cover.
The complete bipartite graph has a minimum vertex cover of size .
A set of vertices is a vertex cover if and only if its complement is an independent set.
Consequently, the number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set (Gallai 1959).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (3)
Related people (2)
Related concepts (36)
NP-completeness
In computational complexity theory, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.
Vertex cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.
Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time.
Related courses (19)
CS-627: Algorithmic Toolbox
This course covers numerous powerful algorithmic techniques (greedy, local search, linear programming, multiplicative weight update, ...). The concepts are studied in clean and simple settings so as t
CS-450: Advanced algorithms
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
CS-250: Algorithms
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma