FACTOID # 28: Austin, Texas has more people than Alaska.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Vertex cover problem

In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karp's 21 NP-complete problems. Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... It was in 1971 that the first NP-complete problem, the boolean satisfiability problem, was discovered and proven to be NP-complete by Stephen Cook. ...

A vertex cover of an undirected graph G = (V,E) is a subset V' of the vertices of the graph which contains at least one of the two endpoints of each edge: simple:Image:6n-graf. ... In computer science, the Vertex Cover Problem is an NP-complete problem in complexity theory. ...

.

In the graph at the right, {1,3,5,6} is an example of a vertex cover.

The vertex cover problem is the optimization problem of finding a vertex cover of minimum size in a graph. The problem can also be stated as a decision problem: In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...

INSTANCE: A graph G and a positive integer k.
QUESTION: Is there a vertex cover of size k or less for G?

Vertex cover is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it. NP-completeness can be proven by reduction from 3-satisfiability or, as Karp did, by reduction from the clique problem. As shown by Garey and Johnson in 1974, vertex cover remains NP-complete even in cubic graphs and even in planar graphs of degree at most 6. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ... In computational complexity theory, the clique problem or k-clique problem is a graph-theoretical NP-complete problem. ... In the mathematical field of graph theory, a cubic graph is a graph where all vertices have degree 3. ... In graph theory, a planar graph is a graph that can be embedded in a plane so that no edges intersect. ...

Vertex cover is closely related to Independent Set problem by this theorem: a graph with n vertices has a vertex cover of size k if and only if the graph has an independent set of size nk. In mathematics, the independent set problem (IS) is a question in combinatorics, known to be an NP-complete problem. ...

One can find a factor-2 approximation by repeatedly taking both endpoints of an edge into the vertex cover, removing them from the graph. No better constant-factor approximation is known; the problem is APX-complete, i.e., it cannot be approximated arbitrarily well. In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...

A brute force algorithm to find a vertex cover in a graph is to choose some vertex and recursively branch into two cases: either take this vertex into the vertex cover, or all its neighbors. This algorithm is exponential in k, but not in the size of the graph, i.e., vertex cover is fixed-parameter tractable with respect to k. In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ... In computer science, fixed-parameter algorithms are an approach to attacking NP-hard problems. ...

In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ...

• Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, 1979.
• Preeti Patil & Sangita Patil. (Lecturer in Vartak Polytechnic) A Guide to the Theory of NP-Completeness. BPB & Co., Mumbai, 2004.
• M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems. Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63. 1974.

Results from FactBites:

 Vertex cover problem - Wikipedia, the free encyclopedia (390 words) In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karp's 21 NP-complete problems. Vertex cover is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it. Vertex cover is closely related to Independent Set problem by this theorem: a graph with n vertices has a vertex cover of size k if and only if the graph has an independent set of size n − k.
More results at FactBites »

Share your thoughts, questions and commentary here