Vertex cover

In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.The problem of finding a minimum vertex cover is a classical optimization problem in computer science and 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. In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.The problem of finding a minimum vertex cover is a classical optimization problem in computer science and 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. Formally, a vertex cover V ′ {displaystyle V'} of an undirected graph G = ( V , E ) {displaystyle G=(V,E)} is a subset of V {displaystyle V} such that u v ∈ E ⇒ u ∈ V ′ ∨ v ∈ V ′ {displaystyle uvin ERightarrow uin V'lor vin V'} , that is to say it is a set of vertices V ′ {displaystyle V'} where every edge has at least one endpoint in the vertex cover V ′ {displaystyle V'} . Such a set is said to cover the edges of G {displaystyle G} . The following figure shows two examples of vertex covers, with some vertex cover V ′ {displaystyle V'} marked in red. A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number τ {displaystyle au } is the size of a minimum vertex cover, i.e. τ = | V ′ | {displaystyle au =|V'|} . The following figure shows examples of minimum vertex covers in the previous graphs. The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph. If the problem is stated as a decision problem, it is called the vertex cover problem: The vertex cover problem is an NP-complete problem: it was one of Karp's 21 NP-complete problems. It is often used in computational complexity theory as a starting point for NP-hardness proofs. Assume that every vertex has an associated cost of c ( v ) ≥ 0 {displaystyle c(v)geq 0} .The (weighted) minimum vertex cover problem can be formulated as the following integer linear program (ILP). This ILP belongs to the more general class of ILPs for covering problems.The integrality gap of this ILP is 2 {displaystyle 2} , so its relaxation gives a factor- 2 {displaystyle 2} approximation algorithm for the minimum vertex cover problem.Furthermore, the linear programming relaxation of that ILP is half-integral, that is, there exists an optimal solution for which each entry x v {displaystyle x_{v}} is either 0, 1/2, or 1.