independent_set (1330B)
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 - [sharp_bis] is the problem of counting independent sets on [graph_bipartite] 23 - it is open whether it admits an [fpras] 24 - [dyer1999counting]: on general graphs there is no [fpras], cf [sharp_is] 25 26 By [duality], counting independent sets exactly is the same as counting [vertex_cover] exactly 27 28 ## [linear_relaxation] 29 30 [fractional_independent_set] 31 - like [fractional_edge_cover] vs [edge_cover] 32 33 See also: [matching], [vertex_cover] 34 35 Up: [graph_substructure] 36 37 Aliases: coclique, anticlique, independent sets, cocliques, anticliques