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