independent_set (1077B)
1 # Independent set 2 3 https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 4 5 An *independent set* is a [subset] of [vertices] of an [undirected_graph] such that no two [vertices] of the [subset] are [adjacent]. Also called a "coclique" or "anticlique", or a "stable" 6 7 ## Connections 8 9 - An independent set is a [clique] of the [complement] of the graph 10 - The [complementation] of an independent set is a [vertex_cover] 11 - and the [complementation] of a [maximum_independent_set] is a [minimum_vertex_cover] 12 13 ## Variants 14 15 - [maximum_independent_set]: [np_hard] to find, mais [ptime] in [graph_bipartite] ([maximum_independent_set_bipartite]) 16 - [maximal_independent_set]: [ptime] to find with [greedy_algorithm] 17 - [generalized_dominating_set] 18 - [independent_set_enumeration] 19 20 ## [counting] 21 22 [independent_set_counting] 23 24 ## [linear_relaxation] 25 26 [fractional_independent_set] 27 - like [fractional_edge_cover] vs [edge_cover] 28 29 See also: [matching], [vertex_cover], [empty_graph] 30 31 Up: [graph_substructure] 32 33 Aliases: coclique, anticlique, independent sets, cocliques, anticliques