vertex_cover (960B)
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 - can be studied in [parameterized_complexity] 21 22 ## Connections 23 24 - 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. 25 - [koenigs_theorem]: on [bipartite_graphs] they have the same size 26 - The [complement] of a vertex cover is an [independent_set] so [minimum_vertex_cover] corresponds to [maximal_independent_set] 27 28 See also: [edge_cover], [vertex_packing], [independent_set], [hitting_set], [set_cover] 29 30 Up: [graph_substructure]