wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

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]