vertex_cover (950B)
1 # Vertex cover 2 3 A vertex cover in a [graph] is a subset of vertices such that every edge is incident to at least one vertex of the subset. 4 5 [linear_relaxation]: [fractional_vertex_cover] 6 - and [dual]: [fractional_edge_packing] 7 8 ## Variants 9 10 - [minimum_vertex_cover] 11 - [minimal_vertex_cover] 12 13 ## [approximation] 14 15 - [vertex_cover_approximation] 16 17 ## [computational_problem] 18 19 - [minimum_vertex_cover] 20 21 ## [theorem]s 22 23 - [koenigs_theorem] in [graph_bipartite] 24 25 ## Connections 26 27 - A vertex cover is at least as large as a [maximum_matching], because each edge in the matching must be covered by a vertex and these vertices must be different for each edge. 28 - [koenigs_theorem]: on [graph_bipartite] they are equal 29 - The [complement] of a vertex cover is an [independent_set] so [minimum_vertex_cover] corresponds to [maximal_independent_set] 30 31 See also: [edge_cover], [vertex_packing], [independent_set], [hitting_set], [set_cover] 32 33 Up: [graph_substructure]